江苏技术师范学院 - 数据结构复习题及答案

一、单项选择题

1、向一个有255个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（B）个元素。

A. 8 B. 127.5 C. 127 D.7 2、带头结点的单链表first为空的判定条件是：(B)

A. first==NULL B. first->link==NULL C. first->link==first D. first!=NULL

3、 设某线性链表的头结点指针为L, L->data表示该链表的结点个数，L->next指向该链表的第一个结点，p指向新建立的结点，其类型与L相同。在建立该链表的过程中，若希望L->next始终指向新输入的结点，可采用如下的C语言语句实现：(A)

A. p->next=L->next, L->next=p，L->data++; B. p->next=NULL, L->next=p, L->data++; C. L->data++, L->next=p->next, p->next=L; D. 以上都不是。

4、设A、B、C三个字符按先后顺序依次进栈，下面哪个序列为不合法的出栈序列：( D)

A. A B C

B. A C B

C. B A C

D. C A B

5、如下陈述中正确的是（ A）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 6、在二叉树的第4层上至多有多少个结点：(B) A. 10个

B. 8个

C. 16个 D. 以上都不是。

7、若一棵二叉树具有8个度为2的结点，则该二叉树的叶子个数是（ A ）

A. 9 B. 11 C. 7 D. 不确定

8、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )

A. e B. 2e C. n2－e D. n2－2e

9、5个不同的数据元素进行直接插入排序，最多需要进行（ B ）次比较。

A.8

B.10

C.14

D.25

10、设有关键码初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X}，新序列

《数据结构》试卷 第 1 页 共 9 页

{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用下列哪种排序方法对初始序列进行第一趟扫描的结果？（C）

A. 直接插入排序 B. 二路归并排序 C. 以第一元素为分界元素的快速排序 D. 基数排序

二、填空题

1、数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D，S)，其中D是数据元素的有限集；S是D上关系的有限集.

2、在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移n-i个元素。 3、队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 设S=”A;/document/Mary.doc”，则strlen(s)=20 “/”的字符定位的位置为3

5、在哈希造表过程中，处理冲突的方法主要有：开放定址法、再哈希法_链地址法、建立一个公共溢出区。

6、所谓稀疏矩阵指的是非零元很少(t<

7 在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为简单路径。

8. 一棵深度为6的满二叉树31_____个分支结点和____23_______个叶子。 9、对于n个记录的表进行2路归并排序，整个归并排序需进行log2n趟（遍）。 10、数据结构有如下四类基本结构：集合、_线性结构、树形结构、图形结构 11、在顺序表中插入或删除一个元素，需要平均移动__表中一半________元素，具体移动的元素个数与__表长和该元素在表中的位置_有关。

12. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 _栈顶_______。不允许插入和删除运算的一端称为___栈底_____。 13、_不包含任何字符（长度为0）的串__称为空串；

14、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址，则数组A的体积（存储量）为____288 B ___________。 15、一棵具有257个结点的完全二叉树，它的深度为__9 _ 三、判断题

( )1、数据结构一般包括数据之间的逻辑结构，数据在计算机中的存储

《数据结构》试卷 第 2 页 共 9 页

方式和数据的运算三个方面。

( ╳)2、单链表从任何一个结点出发，都能访问到所有结点 ( )3、线性表中的每个结点最多只有一个前驱和一个后继。

( )4、一个n X n的对称矩阵，如果采用压缩存储，其容量为n(n+1)/2。 ( )5、 n个结点的树的各结点度数之和为n-1 ( ╳ )6、霍夫曼树一定是满二叉树。

( ╳ )7、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。 ( )8、在有向图G中，所有结点的出度之和一定等于所有结点的出度之和

( ╳)9、顺序查找法与折半查找法对存储结构的要求是：顺序查找与折半查找既适用于顺序表，也适用于链表

( )10、散列表中碰撞的可能性大小与负载因子有关 ( ╳)11、 记录是数据处理的最小单位。

( ╳)12. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

（ ╳)13. 栈和队列是一种非线性数据结构。

( ╳ )14．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列1,5,4,6,2,3。

( )15. 从逻辑结构上看，n维数组的每个元素均属于n个向量。 ( )16. 稀疏矩阵压缩存储后，必会失去随机存取功能。 (╳ )17.二叉树中每个结点的两棵子树的高度差等于1。 ( )18．强连通图的各顶点间均可达。

( )19．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。 四、简答、应用题

1、 设n为正整数，给出下列程序段的时间复杂度。

void func(int n) { int k; k=1; while (k

《数据结构》试卷 第 3 页 共 9 页

k=k*3; }

解：k

所以T（n）=O(log3n) 或O（log (n)）

2、列出先序遍历能得到ABC序列的所有不同的二叉树。

3、已知某算法如下，试说明该算法实现的功能。 #define Max 100

void unknow(int num ,int r) {int st[Max],top=0; while (num!=0) { st[top++]=num%r; num=num/r; }

while (top>0)

cout << st[--top] << “ “; cout << endl; }

解：将十进制数num转换成r进制的数，并输出结果。

4、G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？ 解：设有一个顶点为独立的结点，其余结点为全连通图，则具有28条边的全连通图其有结点数为28<=n(n-1)/2,则n取满足该式的最小值为8，故该图至少有9个顶点。

5、 对于下图所示的有向图G，给出从顶点0到其余各顶点的最短路径及路径长度。

《数据结构》试卷 第 4 页 共 9 页

解1： 0-1 13 2： 0-2 8 3： 0-2-3 13 4： 0-2-3-4 19 5： 0-2-3-4-5 21 6： 0-1-6 20

0 8 13 1 5 9 5 2 32 2 30

3 6 4 7 17 6 6 已知某二叉树先序遍历的结果为：ABDGECFH，其中序遍历的结果为：

DGBEAHFC，试画出这棵二叉树。

2、方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：<{【[(2,3)，6],(7,10)】,32}，(19,21)>

7 、对关键字序列（7，4，1，14，100，30，5，9，20，134），设哈希函数为h(k)=k % 13,试给出表长为13的哈希表（用线性探测开放定址法处理冲突），并求出在等概率情况下，查找成功的平均查找长度。

解：H(7)=7 mod 13 =7 H(4)=4 mod 13 =4 H(1)=1 mod 13 =1

H(14)=14 mod 13 =1 冲突 H1=（14+1） mod 13 =2 H(100)=100 mod 13 =9 H(30)=30 mod 13 =4 冲突 H1=（30+1）mod 13=5 H(5)=5 mod 13 =5 冲突 H1=（5+1）mod 13=6 H(9)=9 mod 13 =9 冲突 H1=（9+1）mod 13=10 H(20)=20 mod 13 =7 冲突 H1=（20+1）mod 13=8

《数据结构》试卷 第 5 页 共 9 页

H(134)=134 mod 13 =4 冲突 H1=（134+1）mod 13=5 冲突 H1=（134+2）mod 13=6 冲突 H1=（134+3）mod 13=7 冲突 H1=（134+4）mod 13=8 冲突 H1=（134+5）mod 13=9 冲突 H1=（134+6）mod 13=10 冲突 H1=（134+7）mod 13=11 冲突

在等概率情况下：ASL=（1*4+5*2+1*8）/10=2.2

6. 已知图1所示的有向图，请给出该图的:(8分)

(1) 每个顶点的入/出度； (2) 邻接矩阵； (3) 邻接表； 顶点 入度 出度 1 2 3 4 (4) 逆邻接表。 5 6

1、对图1所示带权无向图采用prim算法，从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）

分。

3 25 2 1 15 5 20 14 6 4 16 10 图1

2 3 6 7 8 5 12 《数据结构》试卷 第 6 页 共 9 页

S： 顶点号 ①③ ①③② ①③②④ ①③②④⑦ ①③②④⑦⑤ ①③②④⑦⑤⑥

Edge： （顶点，顶点，权值） （ 1 ，2 ，2 ） （ 1 ， 5 ，5 ） （ 2 ， 4 ，3 ） （ 2 ， 7 ，6 ） （ 2 ， 5 ，8 ） ( 7, 6 , 10 )

3、设散列表的长度为11，散列函数为H(k)=k，给定的关键码序列为56,74,23,11,69, 22,59,29。试画出用线性探查法解决冲突时所构成的散列表。

0 11 1 56 2 23 3 69 4 22 5 59 6 7 29 8 74 9 10

2. 假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树边的集合为：{(i,m),(i,n),(b,e),(e,i),(b,d),(a,b), (g,k),(c,g),(c,f), (h,l),(c,h),(a,c)}用树形表示法画出此树。

3．简述树和二叉树之间的区别与联系？

树和二叉树逻辑上都是树形结构，区别有二点：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制。二叉树不是树的特例。

五、算法设计题

1、将一个带头结点的单链表A分解成两个具有相同结构的链表B，C。其中B表的结点是A表中值小于0的结点，而C表的结点为A表中值大于等于0的结点（链表A的元素类型为整形，要求B、C表利用A表的结点。）

算法思路是：先创建两个表头结点B和C，pb和pc分别指向B和C的最后结点。扫描单链表A的所有结点，对于结点*pa, 若其data域值小于0，则将*pa链接到B链表后；否则将*pa链接到C链表后。算法如下：

typedef struct node{ int data;

struct node *next; } Lnode;

《数据结构》试卷 第 7 页 共 9 页

void split(Lnode *A, Lnode *B, Lnode *C); {Lnode *pa=A->next, *pb,*pc; B=new Lnode; //创建头结点 C=new Lnode; //创建头结点 pb=B;pc=C;

while(pa!=NULL){

if (pa->data<0){ //小于0的数据插入B队列 pb->next=pa;pb=pa; }

else { //大于0的数据插入C队列 pc->next=pa; pc=pa; }

pa=pa->next; }

pb->next=pc->next=NULL;

2. list指向带头结点的非空线性链表，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。

解：LinkedList delinsert（LinkedList list）

∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。

∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针

pre=list； ∥pre指向链表中数据域最小值结点的前驱。 q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->link!=null）

{if（p->link->datadata）{pre=p；q=p->link；} ∥找到新的最小值结点； p=p->link； }

if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link； ∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q； }

}∥算法结束

[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。

3，已知二叉树采用二叉链表存储，试编写一个算法，计算二叉树中叶子结点的个数。

2. 解：

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {

if(!T) return 0; //空树没有叶子

《数据结构》试卷 第 8 页 共 9 页

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数

}//LeafCount_BiTree

4. 写出求二叉树深度的算法。

1．int Get_Depth(Bitree T) //求子树深度的递归算法 {

if(!T) return 0; else {

m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }

}//Get_Depth

5．已知11个元素的有序表为（05,13,19,21,37,56,64,75,80,88,92）, 请写出折半查找的算法程序，查找关键字为key的数据元素

2．解：折半查找的C程序有很多参考资料，注意此题要求是整型量。 折半查找的一个递归算法如下，形式非常简洁！

int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 {

if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2;

if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key)

return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); }

}//Search_Bin_Recursive }

《数据结构》试卷 第 9 页 共 9 页

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