数据结构练习题

10、已知图G=（V, E），其中V={v1,v2,v3,v4,v5}, E={, , , , ), }；画出这个图的图形并写出所有的拓扑序列。

11、设有关键码序列{20，35，40，15，30，25，38}，请给出平衡二叉树的构造过程（只需要给出不平衡时到平衡的过程即可）。

12、已知散列函数为H(K)=K mod 13,健值序列为11，31，15，44，06，78，12，25，38，84，19，49，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。

13、对于下列一组关键字47，56，15，45，80，19，9，61，试写出快速排序每一趟的排序结果。

14、对下面的关键字集（30，15，21，40，25，26，36，37），若查找表的装填因子为0.8，采用线性探测再散列解决冲突：（1）设计哈希函数；（2）画出哈希表；（3）求查找成功的平均查找长度。

15、按顺序输入下列顶点对: (V1, V2)、(V1, V6)、(V2, V6)、(V1, V4)、(V6, V4)、(V1,

V3)、(V3, V4)、(V6, V5)、(V4, V5)、(V1, V5)、(V3, V5)。（顶点序列为：V1，V2，V3，V4，V5，V6）

（1）画出相应的邻接表。

（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树。

五、算法与程序设计

1、阅读算法完成题目要求：

（1）说出下列算法的功能。

template struct Binnode { T data;

Binnode *prior, *next; };

bool Unknown (Binnode *first) { Binnode *p,*q;

p=first->next; q=first->prior;

while(p!=q && p->prior!=q)

if(p->data==q->data) {

p=p->next; q=q->prior; }

else return 0; return 1; }

（2）根据下列算法和输入的数据画出生成的链表形式。

template

LinkList:: LinkList( int n) { first=new Node;

Node *s; T x;

first->next=NULL;; for (int i=0; i>x;

s=new Node; s->data=x;

s->next=first->next; first->next=s; } }

输入数据为：10 9 8 7 6 5

（3）说出下列算法的功能，它是采用什么结构实现的。

template

void BiTree::Unknown (BiNode *root) { const int MaxSize = 100; int front = 0; int rear = 0;

BiNode* Q[MaxSize]; BiNode* q; if (root==NULL) return; else{ Q[rear++] = root; while (front != rear) { q = Q[front++]; cout<data<<\ if (q->lchild != NULL) Q[rear++] = q->lchild; if (q->rchild != NULL) Q[rear++] = q->rchild; } } }

（4）阅读下列算法求出调用该算法后输出结果。

void AE(Stack& S)

{

InitStack(S); Push(S,10); Push(S,20); Push(S,30);

int x=Pop(S)+2*Pop(S); Push(S,x);

int i,a[4]={7,9,15,18};

for(i=0;i<4;i++) Push(S,a[i]);

while(!StackEmpty(S)) cout<

输出结果为：

（5）阅读下列算法：（设L是带头结点的单链表的头指针，并为已知的LinkList类型） void DeleteX(LinkList &L){ p=L－>next;

while(p&& p－>next－>data!=x){ q=p;p=p－>next; }

if(p){

q－>next=p－>next; free(p); }

}

算法的功能：

（6）设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能。

void F1(Linklist &L){

p=L→next; pre=p;

while(p){ if(p→data

pre=p; p=p→next; }

printf(pre→data);

if(pre→next && pre→data%2==0) {

p=pre→next,

pre→next=p→next;free(p);

}

}

算法功能：

2、程序设计

(1) 设有一单链表L，结点结构为data|next，编写算法判断该单链表L中的元素是否

成等差关系，即：设各元素值次为a1,a2,a3,…,an，判断ai+1-ai=ai-ai-1是否成立。若是返回1，否则返回0。

函数说明为：int dengcha(Node *L)；

(2)写出二分查找的非递归算法。(要求统计查找过程中元素的比较次数)

函数说明为： int binsearch(int r[ ], int n,int k)；

(3)设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。

函数说明为：Void Linklist::purge(Node * first)；

(4)写出图在邻接表存储结构下广度优先的遍历算法。 函数说明为：

template

函数说明为：void ALGraph ::BFSTraverse(int v)；

（5）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

（6）设计一算法判断一个单链表中的元素是否对称。

（7）设计在链式存储结构上交换二叉树中所有结点左右子树的算法。