数据结构试题及答案(1)

试题一

一、单选题（每题 2 分，共20分）

1、对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度

2、在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。

A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;

C. p->next=HL; p=HL; D. HL=p; p->next=HL;

3、对线性表，在下列哪种情况下应当采用链表表示？( B )

A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

4、一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )

A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5、AOV网是一种（ D ）。

A．有向图 B．无向图 C．无向无环图 D．有向无环图

6、采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突

C．与链接法处理冲突相同 D．高于二分查找

7、若需要利用形参直接访问实参时，应将形参变量说明为（ D）参数。 A．值 B．函数 C．指针 D．引用

8、在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。

A．行号 B．列号 C．元素值 D．非零元素个数 9、快速排序在最坏情况下的时间复杂度为（ D ）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10、从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)

二、填空题（每题 6 分，共24分）

1. 数据结构是指数据及其相互之间的____联系__________。当结点之间存在M对N（M：N）的联系时，称这种结构为______图或图结构_____________。 2. 队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。

3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0_____________。

4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为

____O_____，在表尾插入元素的时间复杂度为______O(n)______。

5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿__128___＿个字节。W中第6 行的元素和第4 列的元素共占用＿__44_____＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿_____108___＿。

6. 广义表A= (a,(a,b),((a,b),c)),则它的深度为______3______，它的长度为________3____。

7. 二叉树是指度为2的________有序____________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____n-1________。

8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个____有序序列__________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的____后缀表达式______________。

9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____2n________个，其中______n-1_________个用于指向孩子，__________n+1_______个指针是空闲的。

10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为__2i+1______,右孩子元素为____2i+2___________，双亲元素为__(i-1)/2__________。

11. 在线性表的散列存储中，处理冲突的常用方法有________开放定址法________________和____________链接法_________________两种。

12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______快速________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用__________归并______________排序。

三、 运算题（每题6分，共24分） 1. 1. 已知一个6?5稀疏矩阵如下所示，

?0?0??0??0?5??0?00000000070000001?0??0???2?0??0??

?10

试： 5 5 （ 1 1）5 写出它的三元组线性表；1 6 3 -1 4 5 -2 1. （1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分) 5 1 5 （2） 三元组线性表的顺序存储表示如图7示。 6 3 7 图7

（2） 给出三元组线性表的顺序存储表示。

2

2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。

3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 4. 已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序

图6

号从小到大的次序链接的，按主教材

中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

四、 阅读算法（每题7分，共14分） 1. int Prime(int n)

{ int i=1;

int x=(int) sqrt(n);

while (++i<=x)

if (n%i==0) break; if (i>x) return 1; else return 0; }

(1) 指出该算法的功能；

(2) 该算法的时间复杂度是多少？ 2. 写出下述算法的功能： void AJ(adjlist GL, int i, int n) {

Queue Q; InitQueue(Q); cout<

while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) { int j=p->adjvex; if(!visited[j]) { cout<next; } }

}

五、 算法填空（共8分）

如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {

int low=0; int high=n-1;

while (low<=high)

{

int mid=_______________________________；

if (K==A[mid].key) return mid; //查找成功，返回元素的下标

else if (K<[mid].key)

______________________________________; //在左子表上继续查找

else __________________________________; //在右子表上继续查找

}

return -1; //查找失败，返回-1 }

六、 编写算法（共8分）

HL是单链表的头指针，试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL)

参考答案

一、 单选题（每题2分，共20分）

1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C 二、 填空题（每空1分，共26分） 1. 联系 图（或图结构） 2. 尾 首 3. top==0

4. O（1） O（n） 5. 128 44 108 6. 3 3

7. 有序 n-1

8. 有序序列 后缀表达式（或逆波兰式） 9. 2n n-1 n+1

10. 2i+1 2i+2 (i-1)/2 11. 开放定址法 链接法 12. 快速 归并

三、运算题（每题6分，共24分）

1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)

（3） 三元组线性表的顺序存储表示如图7示。

6 1 3 4 5 6 5 5 2 5 1 3 5 1 -1 -2 5 7 图7

12. 归并

三、 运算题（每题6分，共24分）

1. 线性表为：（78，50，40，60，34，90）

?0?1??1??1?2. 邻接矩阵：?01110?0101??1011??0101?1110??

邻接表如图11所示：

图11

3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4. 见图12

2 4 4 2 2

2 4 4 5 4 5

8 2

3 5

4 8 图12

四、 阅读算法（每题7分，共14分） 1. （1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 2. 递归地后序遍历链式存储的二叉树。 五、 算法填空（每空2分，共8 分） true BST->left BST->right 六、编写算法（8分）

int CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//CountX

2 4 8 3 5

试题三

一、单选题（每小题2分，共8分）

1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( C )。

A n B n/2 C (n+1)/2 D (n-1)/2 2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( D )。

A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 栈的插入和删除操作在（ A）进行。

A 栈顶 B 栈底 C 任意位置 D 指定位置 4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ B ）

A 24 B 71 C 48 D 53 二、填空题（每空1分，共32分）

1、数据的逻辑结构被分为___集合______ _、 _线性__________ 、____树____和___图_____四种。

2、一种抽象数据类型包括_____数据描述_________和_____操作声名________两个部分。

3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为____________（38,56,25,60,42,74）； a 0 1 2 3 4 5 6 7 8

data

60 56 42 38 74 25 next

4 3 7 6 2 0 1

4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为_____HL next NULL___________和__HL HL next;__________________。

5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向

队首元素的___前一个位置________，该循环队列的最大长度为____n-1______。

6、当堆栈采用顺序存储结构时，栈顶元素的值可用___S.STACK【S.top】_________表示；当堆栈采用链接存储结构时，栈顶元素的值可用________HS______date _表示。

7、一棵高度为5的二叉树中最少含有_____5____个结点，最多含有_____31___个结点；

一棵高度为5的理想平衡树中，最少含有_____5____个结点，最多含有____31_____个结点。

8、在图的邻接表中，每个结点被称为__边结点__________，通常它包含三个域：一是____邻接点域_________；二是__权威_________；三是______链域_______。

9、在一个索引文件的索引表中，每个索引项包含对应记录的__索引值域_______和____开始位置域_______两项数据。

10、 假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为___10______个，树的深度为__3_______,树的度为____3____, 结点H的双亲结点为____B___,孩子结点为___I和J;____________ 。

11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__O(log2n)_______,整个堆排序过程的时间复杂度为___O(nlog2n)_____________。

12、 在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于____m__个，则必须把它分裂为_____m-1__个结点。

三、运算题（每小题6分，共24分）

1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。

2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散

列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

4、已知一个图的顶点集V各边集G如下：

V = {0，1，2，3，4，5，6，7，8，9}；

E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），

（5，8），（5，9），（6，7），（7，8），（8，9）}

当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。

假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。

图 深度优先序列 广度优先序列 邻接矩阵表示时

邻接表表示时

四、阅读算法，回答问题（每小题8分，共16分）

1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 写出输出结果。

# include < iostream.h> # include < stdlib.h >

consst int stackmaxsize = 30;

typedef int elemtype; struct stack {

elemtype stack [stackmaxsize]; int top; };

# include “stack.h” Void main ( )

{

stack a; initstack(a);

int x; cin >>x;

while (x! = -1) { push (a, x ); cin >>x;

}

while (!stackempty (a)) cout <

1，请 –cout <

}

该算法的输出结果为：

__________________________________________________________. 2、阅读以下二叉树操作算法，指出该算法的功能。 Template void BinTree ：：

unknown (BinTreeNode*t) {

BinTreeNode< Type> *p =t, *temp; if (p!=NULL) {

temp = p→leftchild;

p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild);

undnown(p→rightchild); } }

该算法的功能是：________________________________

五、算法填空，在画有横线的地方填写合适的内容（10分）

对顺序存储的有序表进行二分查找的递归算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) {

if (low <= high) {

int mid = 1

if ( K= = A[ mid ].key ) return mid;

else if ( K < A[mid].key) return 2 else

return 3 }

else

return 4

六、编写算法（10分）

编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为, an，an-1，……a1。

Void contrary (Lnode * & HL)

数据结构试题（答案）

一、单选题（每小题2分，共8分） 1 2 3 题 号 C D 答 案 二、填空题（每空1分，共32分） 1： 集合、线性、树、图； 2： 数据描述、操作声名；

3： （38，56，25，60，42，74）；

4： HL→next =NULL； HL=HL→next； 5： 前一个位置； n-1；

6： S.stack [S.top]; HS→data; 7： 5 31

8： 边结点、邻接点域、权域、链域； 9： 索引值域、开始位置域； 10： 10、3、3、B、I和J； 11： O（log2n）、O(nlog2n); 12： m 、 m - 1

三、运算题（每小题6分，共24分） 1、

划分次序 第一次 第二次 第三次 第四次 第五次 第六次 A 4 B 划分结果 [38 24 40] 46 [56 80 95 79] 24 [38 40] 46 [56 80 95 79] 24 38 40 46 [56 80 95 79] 24 38 40 46 56 [80 95 79] 24 38 40 46 56 79 [80 95] 24 38 40 46 56 79 80 95 2、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASL SUCC=14/10= 1.4

3、此二叉树的后序遍历结果是：EDCBIHJGFA 4、

图 邻接矩阵表示时 邻接表表示时 深度优先序列 0，1，2，8，3，4，5，6，7，9 0，4，3，8，9，5，6，7，1，2 广度优先序列 0，1，4，2，7，3，8，6，5，9 0，4，1，3，7，2，8，6，9，5 四、阅读算法，回答问题（每小题8分，共16分） 1、 1、 该算法的输入结果是：34 91 30 45 63 78

2、 2、 该算法的功能是：交换二叉树的左右子树的递归算法。 五、算法填空，在画有横线的地方填写合适的内容（10分） 1、1是：（low + high）/2;

2是： Binsch(A,low,mid–1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1；

六、编写算法（10分） 根据编程情况，酌情给分。 {

Lnode *P=HL; HL=NULL; While (p!=null) {

Lnode*q=p; P=p→next; q→next=HL; HL=q; } }

试题四

第一部分 选择题(30分)

一、项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1．算法指的是（ ）

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可 C．必须是连续的

D．和头结点的存储地址相连续

3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）

A．O（1） B．O（n） C．O（m） D．O（m+n） 4．由两个栈共享一个向量空间的好处是：（ ） A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率

5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 6．如下陈述中正确的是（ ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串

7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最

n坏情况下的时间复杂度是（ ）

A．O（3） B．O（n） C．O（n2） D．O（n3） 8．一个非空广义表的表头（ ）

A．不可能是子表 B．只能是子表

C．只能是原子 D．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表

?0?806??03 3 ?0 ?5 ?0?772 0?80006????0??0? 对应的稀疏矩阵是（ ） 00000A.?0B.?00??5????0704D.? 052000?C.????0000?????5040? ??05? ???? ?0000? ?0?8?8000003006?6?000???400?0??000?0??040??0 ?300??

10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )

A．4 B．5 C．6 D．7

11．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e

12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi

相关的所有弧的时间复杂度是( )

A．O(n) B．O(e) C．O(n+e) D．O(n*e)

13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进

行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84

15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）

A．选择排序 B．希尔排序 C．归并排序 D．快速排序 14．适于对动态查找表进行高效率查找的组织结构是（ ）

A．有序表 B．分块有序表 C．三叉排序树 D．线性链表 15．不定长文件是指（ ）

A．文件的长度不固定 B．记录的长度不固定

C．字段的长度不固定 D．关键字项的长度不固定

第二部分 非选择题（共70分）

二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，

共20分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。

16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是

独立于计算机的。

17．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。 18．栈顶的位置是随着 操作而变化的。

19．在串S=“structure”中，以t为首字符的子串有 个。

20．假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其

中B[0]存储矩阵中第1个元素a1,1,则B[31]中存放的元素是 。

21．已知一棵完全二叉树中共有768结点，则该树中共有 个叶子结点。

22．已知一个图的广度优先生成树如右图所示，则与此相 应的广度优先遍历序列为 。

23．在单链表上难以实现的排序方法有 和 。 24．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进

行的关键字比较次数为 。 25．多重表文件和倒排文件都归属于 文件。 三、解答题（本大题共4小题，每小题5分，共20分） 26．画出下列广义表的共享结构图形表示 P=（（（z）,(x,y)）,((x,y),x),(z)） 27．请画出与下列二叉树对应的森林。

28．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示

a

b (1)画出该图的图形；

c （2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，d 写出相应的遍历序列。 e

29．已知一个散列表如下图所示： ?01001??10010????00011????01101???10110??35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数为h(key)=key, 处理冲突的方法为双重散列法，探查序列为： hi=(h(key)+i*h1(key))%m i=0,1,?，m－1 其中

h1(key)=key+1 回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？

??1当s1?s25分，共20分） 四、算法阅读题（本大题共4小题，每小题??0当s1?s230．下列算法的功能是比较两个链串的大小，其返回值为： ?1当s?s12 comstr(s1,s2)=?请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2) {//s1和s2为两个链串的头指针 while(s1&&s2){

if(s1－>datedate)return－1； if(s1－>date>s2－>date)return1； ① ； ② ； }

if( ③ )return－1； if( ④ )return1； ⑤ ； } ① ② ③ ④ ⑤

31．阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }

return L； }

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。

32．假设两个队列共享一个循环向量空间（参见右下图），

其类型Queue2定义如下： typedef struct{

DateType data[MaxSize]；

int front[2],rear[2]；

}Queue2；

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。

int EnQueue (Queue2*Q,int i,DateType x)

{//若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if(i<0||i>1)return 0；

if(Q－>rear[i]==Q－>front[ ① ]return0； Q－>data[ ② ]=x； Q－>rear[i]=[ ③ ]; return1；

} ① ② ③

33．已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef struct node { DateType data； Struct node * next；

}ListNode；

typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) {

LinkList s； If(T){

Inorder(T－>lchild)；

If ((!T－>lchild)&&(!T－>rchild)){

s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data； s－>next=Leafhead； Leafhead=s； }

Inorder(T－>rchild)； } }

对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

（2）说明该算法的功能。

五、算法设计题（本题共10分）

34．阅读下列函数arrange()

int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h；

while(i

while(i=x)j--； while(i=x)i++；

if(i

{ t=a[j]；a[j]=a[i]；a[i]=t；} }

if(a[i]

（1）写出该函数的功能；

（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进

行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。

数据结构试题参考答案

一、 单项选择题（本大题共15小题，每小题2分，共30分） 1．D ２．Ｂ ３．Ｃ ４．Ｂ ５．Ｄ ６．Ａ ７．Ｃ ８，Ｄ ９，Ａ 10．Ｃ 11．Ｄ 12．Ｃ 13．Ｄ 14．Ｃ 15．Ｂ 二、填空题（本大题共10小题，每小题2分，共20分） 16．存储（或存储结构） 17.p－＞next－＞next 18．进栈和退栈 19．12 20．a4,8 21．384 22．abefcdg 23．快速排序、堆排序、希尔排序 24．２ 25.多关键字 三、解答题（本大题共4小题，每小题5分，共20分）

26．

图1 图2 27．

28．该图的图形为：

深度优先遍历序列为：abdce 广度优先遍历序列为：abedc 29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１； 3?2?1?1?29ASL??55 （２）平均查找长度

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30． ①S1=S1－>next ②s2=s2－>next

③s2(或s2!=NULL或s2&&!s1) ④s1(或s1!=NULL或s1&&!s2) ⑤return 0

31.（1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 32. ①(i＋1)%2(或1－i) ②Q－>rear[i]

③(Q－>rear[i]＋)%Maxsize 33.(1)Leafhead F H G D ∧ （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以

Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。

五、算法设计题（本题共10分） 34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所

有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。

（2）int f(int b[],int n) 或 int f(int b[],int n) { {

int p,q； int p,q；

p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； return q－p； return p－q； } }

试题五

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。 (A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3 (D) 2

7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。 (A) 100 (B) 40 (C) 55 (D) 80

8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ ）。 (A) 3 (B) 4 (C) 5 (D) 1

9．根据二叉树的定义可知二叉树共有（ ）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10. 10. 设有以下四种排序方法，则（ ）的空间复杂度最大。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希尔排序

二、填空题(30分)

1. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素

所在的位置，则出队列的语句为F =____________;。 2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。

3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。

4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。

5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。 6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。

7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。

8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。

9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。

int index(char s[ ], char t[ ]) { i=j=0;

while(i

if (j==strlen(t))return(i-strlen(t));else return (-1); }

10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。

三、应用题（30分）

1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。

2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。

4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。

5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。

四、算法设计题(20分)

1. 1. 设计判断单链表中结点是否关于中心对称算法。 2. 2. 设计在链式存储结构上建立一棵二叉树的算法。 3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。

数据结构试卷参考答案

一、选择题 1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B 二、填空题 1. (F+1) % m 2. O(n)，O(n) 3. 2n，n+1

4. s->next=p->next; s->next=s 5. n, 2e 6. m=2e 7. CBA 8. 4，16

9. i-j+1，0

h010. n-1

h1??8三、应用题

h21. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。 h3??102. 哈夫曼树略，WPL=78 h4??25??32h5??6801，2(5，316，42156，187，23) 3. (18,5,16,19,21,23)，194. 线性探测：?8?1025322768 链地址法：h6??27

5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)} 四、算法设计题

1. 设计判断单链表中结点是否关于中心对称算法。

typedef struct {int s[100]; int top;} sqstack; int lklistsymmetry(lklist *head) {

sqstack stack; stack.top= -1; lklist *p;

for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0);

return(1); }

2. 设计在链式存储结构上建立一棵二叉树的算法。

typedef char datatype;

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; void createbitree(bitree *&bt)

{

char ch; scanf(\ if(ch=='#') {bt=0; return;}

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }

3. 设计判断一棵二叉树是否是二叉排序树的算法。

int minnum=-32768,flag=1;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0)

{inorder(bt->lchild); inorder(bt->rchild);}

}

if(minnum>bt->key)flag=0;

minnum=bt->key;

14. return(t)，t=t->rchild

第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。

三、算法设计题

1. 设计在单链表中删除值相同的多余结点的算法。

typedef int datatype;

typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) {

lklist *p,*q,*s;

for(p=head;p!=0;p=p->next) {

for(q=p->next,s=q;q!=0; )

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } }

2. 设计一个求结点x在二叉树中的双亲结点算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) {

if (bt!=0 && flag==0)

if (bt->data==x) { flag=1; return;}

else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } }

void parent(bitree *bt,char x) {

int i;

preorder(bt,x);

for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\

else if (i<=r) printf(\}

试题八

一、选择题(30分)

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。

2

(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 (A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1

3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 (A) n (B) e (C) 2n (D) 2e 4．在二叉排序树中插入一个结点的时间复杂度为（ ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)

5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 (A) n (B) n-1 (C) m (D) m-1

6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 7．设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 8．下列四种排序中（ ）的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆

9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l

10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不

超过（ ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)

二、填空题(42分)

1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。

2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。

3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。 4． 深度为k的完全二叉树中最少有____________个结点。

5． 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元素开始进行筛选。

6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。

7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。

8． 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。

9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。

10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。

11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。

12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。

13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。

14．设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。

typedef struct node {int key; struct node *next;} lklist; void createlkhash(lklist *hashtable[ ]) {

int i,k; lklist *s;

for(i=0;i

s=(lklist *)malloc(sizeof(lklist)); s->key=a[i];

k=a[i] % p; s->next=hashtable[k];_______________________; } }

三、算法设计题(28分)

1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 3. 在链式存储结构上建立一棵二叉排序树。

参考答案

一、选择题

1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A

二、填空题

1. O(n2)，O(nlog2n)

2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink 3. 3 4. 2k-1 5. n/2 6. 50，51

7. m-1，(R-F+M)%M 8. n+1-i，n-i

9. (19，18，16，20，30，22) 10. (16，18，19，20，32，22) 11. A[i][j]=1 12. 等于 13. BDCA

14. hashtable[i]=0，hashtable[k]=s

三、算法设计题

1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)

{

lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {

head=p->next; p->next=0;

if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}

else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } }

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

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->lchild=bt->rchild; bt->rchild=p; }

3. 在链式存储结构上建立一棵二叉排序树。

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) {

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt) {

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

试题九

一、选择题(30分)

1．数据的最小单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20

3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。

(A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85

4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。 (A) “STRUCTURE” (B) “DATA” (C) “ASTRUCTUR” (D) “DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)

6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ ）。 (A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2Nl+3N2+……+(m+1)Nm

7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 (A) 25 (B) 10 (C) 7 (D) 1

8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb

9．设输入序列是1、2、3、??、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ ）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定

10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为

基准而得到一趟快速排序的结果是（ ）。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88 (C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80

二、填空题(共30分)

1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。

2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。 3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

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

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

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