数据结构练习题2

练习题

一、 填空题

1、__数据项_是数据的最小单位，_数据元素_____是讨论数

据结构时涉及的最小数据单位。

2、设一棵完全二叉树具有100个结点，则此完全二叉树有 49

个度为2的结点。

3、在用于表示有向图的邻接矩阵中，对第i列的元素进行

累加，可得到第i个顶点的__入____度。

4、已知一棵度为3的树有2个度为1的结点，3个度为2

的结点，4个度为3的结点，则该树中有_____12___ 个叶子的结点。根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

5、有一个长度为20的有序表采用二分查找方法进行查找，

共有＿4＿＿＿＿＿个元素的查找长度为3。

6、对于双向链表，在两个结点之间插入一个新结点需要修

改的指针共_4___个。

删除一个结点需要修改的指针共______2___个。 7、已知广义表LS=(a,(b,c,d),e)，它的深度是______2____，

长度是______3____。

8、循环队列的引入是为了克服___假溢出_______。 9、表达式

a*(b+c)-d/f

的后缀表达式是

__abc+*df/-_________。

10、数据结构中评价算法的两个重要指标是 时间和空间复杂度 。

11、设r指向单链表的最后一个结点，要在最后一个结点之

后插入s所指的结点，需执行的三条语句是_r->next=s_____；r=s; r->next=null;。

12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输

入序列为

1，2，3，4，5，经过

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_23______，而栈顶指针值是___1012____H。设栈为顺序栈，每个元素占4个字节。

13、模式串P=‘abaabcac’的next函数值序列为_01122312_______。

14、任意连通图的连通分量只有一个，即是 其自

身 。 15、栈的特性是 后进先出 。

16、串的长度是 串中所包含的字符数 。

17、如果一个有向图中没有＿回路＿＿＿＿＿，则该图的全

部顶点可能排成一个拓扑序列。

18、在具有n个叶子结点的哈夫曼树中，分支结点总数为

n-1 。

19、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于____n/m____。

20、排序的主要目的是为了以后对已排序的数据元素进行 查找 。 21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为_O（n）_______。 22、线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_表长的一半_______。

23、两个栈共享空间时栈满的条件_____top2=top1+1__。 24、深度为H 的完全二叉树至少有_ 2^（H-1） __个结点；至多有_ 2^H-1__个结点；H和结点总数N之间的关系是 H=log2N+1 __。

25、在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是_______1368 11 13 16 19___。

26、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_____7___次就可以断定数据元素X是否在查找表中。

27、根据初始关键字序列(17，25，3，39，12)建立的二叉排序树的高度为___3_________。

28、设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

29、 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。

30、 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。

31、 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。

32、 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。

33、typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________; }

34、 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。 void bubble(int r[n]) {

for(i=1;i<=n-1; i++) {

for(exchange=0,j=0; j<_____________;j++) if

(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}

if (exchange==0) return； } }

35、 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。

struct record{int key; int others;}; int bisearch(struct record r[ ], int k)

34．哈夫曼树中没有度数为1的结点。（N ）

35．对连通图进行深度优先遍历可以访问到该图中的所有顶

点。（Y ）

36．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（Y）

37．由树转化成二叉树，该二叉树的右子树不一定为空。（Y ）

38．线性表中的所有元素都有一个前驱元素和后继元素。（ N）

39.带权无向图的最小生成树是唯一的。（ N ） 四、应用题

1、已知一棵二叉树的先根序列和中根序列分别为

ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树，并给出其后序序列。

2、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）

B A D E F H G K L M N O

P I J C

3、已知无向图如下所示：

（1）．给出从V1开始的广度优先遍历序列；（2）．画出它的邻接表；

（3）．画出从V1开始深度优先遍历生成树

4、假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，请先构建一棵哈夫曼树，计算其WPL值，并为这8个字母设计相应的哈夫曼编码。 5

、

已

知

一

表

为

（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中顺序依次插入初始为空的二叉排序树，要求：

(1)画出建立的二叉排序树（值的大小以字母顺序为准）。 (2)对该二叉排序树作中序遍历，试写出遍历序列。 (3)求出在等概率情况下查找成功的平均查找长度。

6、已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7};

E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,

(4,6)4,(5,7)20};

按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。

________, ________, ________, ________, ________, ________, ________。

7、已知散列函数为H(K)=K mod 11,健值序列为{47，7，29，11，16，92，22，8，3}哈希表长为11，采用线性探测法处理冲突，试构造闭散列表，并计算查找成功和不成功的平均查找长度。

8、已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试完成下列各题。

(1) 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。

(2) 输出最小值后，如何得到次小值。（并画出相应结果图）。

9、下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出一个方案。

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

v1 19 16 21 11 v2 6 6

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

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

13、对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果。

14、在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。

A 0 1 2 3 4 5 6 7 Data Next

五、算法与程序设计 1、阅读算法完成题目要求：

3 5 7 2 0 4 1 60 50 78 90 34 40

}

算法的功能： 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）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

（5）int Width(BiTree bt)

{if (bt==null) return (0); else {BiTree Q[];

front=1;rear=1;last=1;

temp=0; maxw=0;

Q[rear]=bt;

while(front<=last)

{p=Q[front++]; temp++; if

Q[++rear]=p->lchild;

if

Q[++rear]=p->rchild;

if (front>last) {last=rear;

if(temp>maxw) maxw=temp;

temp=0;

}

}

(p->rchild!=null) (p->lchild!=null)

return (maxw);

}

（6）假设哈希函数为H（key）,编写用链地址法解决冲突的哈希表的插入和删除算法。

void F2( HashTable &H, keytype Key){//哈希

表插入，用链地址法解决冲突

i=H(Key);;// 获取哈希地址

if(H[i]==Null){

s=(Linklist)malloc(sizeof(Lnode))

;

s→data=key; s→next=H[i]; H[i]=s; }//if

else{ p=H[i];// 查找

while(p&&p→data!=key) p=p→

next;

if(p→data==key) exit(1);

else{ s=(Linklist)malloc(sizeof(L

node));// 产生新结点，插入表头

s→next=H[i]; H[i]=s; }// else

}//else

}//F2

void Delete_HS(HashTable &H, KeyType key){

//哈希表删除，用链地址法解决冲突

i=H(key); //获得哈希地址 if(H[i]= =Null) exit(1);

p=H[i];q=p; // p为工作指针，q为p前趋

while(p&&p→data!=key) {//查找

q=p; p=p→next; }//while

if(!p) exit(1);

if(q==H[i]){ //key为第一结点 H[i]p→next; free(p); }// if

else{

q→next=p→next;

free(p);

}//else }//Delete_HS

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

树的算法。 typedef

struct

node

{int

data;

struct

node

*lchild,*rchild;} bitree; void swapbitree(bitree *bt) {

bitree *p; if(bt==0) return;

swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild;

bt->rchild=p;}

bt->lchild=bt->rchild;

本文来源：https://www.bwwdw.com/article/vg73.html