数据结构练习题 下载本文

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)设计在链式存储结构上交换二叉树中所有结点左右子树的算法。