数据结构C++考试题及答案

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。 A、不确定 B、2n C、2n+1 D、2n-1 2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表 4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。 A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。

A、空或只有一个结点 B、高度等于其结点数

C、任意结点无左孩子 D、任意结点无右孩子

6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的 是（ ）。

A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

7、快速排序算法在最好情况下的时间复杂度为（ ）。

A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn) 8、已知数据表 A中每个元素距其最终位置不远，则采用（ ）排序算法最 省时间。

A、堆排序 B、插入排序 C、直接选择排序 D、快序排序

9、带权有向图G用邻接矩阵 A存储，则顶点 i的入度为 A中（ ）。

A、第 i行非∞的元素之和 B、第 i列非∞的元素之和

C、第 i行非∞且非 0的元素之和 D、第 i列非∞且非 0的元素之和 10、在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比 较次数的数量级为（ ）。

A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn) 二、判断题 （认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，

共10分）

1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可

访问该图的每个顶点。 ( )

2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅

与表的个数有关，而且与每一块中的元素个数有关。 ( ) 3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 ( ) 4、图G的最小生成树的代价一定小于其他生成树的代价。 ( ) 5、已知一棵树的先序序列和后序序列，一定能构造出该树。 ( ) 6、对一个堆按层次遍历，不一定能得到一个有序序列。 ( )

7、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT

中的结点也一定是叶子结点。 ( ) 8、不管 ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Push(x,S) 的

耗时均为 O(n)。 ( ) 9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入 上去，一定能得到原来的二叉排序树。 ( ) 10、快速排序是排序算法中最快的一种。 ( ) 三、填空题（每小题2分，共20分） 1、在双向循环表中，在 p所指的结点之后插入指针 f所指的结点，其操作为 ： ___ ______=p;f→next=p→next;_____=f; p→next=f。

2、在有序表 A[1?20]中，采用二分查找算法查找元素值等于 A[12]的元素，所比较过的元素的下标依次为__________。

3、若某串的长度小于一个常数，则采用_________存储方式最节省空间。 4、在有 n个顶点的有向图中，每个顶点的度最大可达_________。

5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 __________。

6、设键值序列为{K1，K2，?，Kn},用筛选法建堆则必须从第_______个元 素开始筛选。

7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_________。 8、直接选择排序算法在最好情况下所作的交换元素的次数为___ _____。

9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行_______比赛。 10、下列排序算法中， 占用辅助空间最多的是_________( 堆排序， 希尔排序，

快速排序，归并排序)。

四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？ 2、设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答以下问题：

（1）设计一个适合该散列表的散列函数。

（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多少？

3、对 n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下

列有关问

（1）图中有多少条边？

（2）任意两个顶点 i和 j是否有边相连？ （3）任意一个顶点的度是多少？

4、已知下面二叉排序树的各结点的值依次为1?9，请标出各结点的值。

5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同形态有哪些？ 6、分析以下程序段中语句x=x+y的执行次数。 x=0; y=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++) for(int k=1;k<=j;k++) x=x+y;

五、算法设计题（每题15分，共30分）

说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。 1、假设以二叉链表作为二叉树存储结构，其类型定义如下： typedef struct node { char data;

struct node *lchild,*rchild;//左右孩子指针 }BinTNode,*BinTree;

写一函数，完成以下功能：

对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩子设置为左孩子。

2、试设计将数组 A[0?n-1]中所有奇数移到所有偶数之前的算法。要求不另增加存储空间且时间复杂度为O(n)。

数据结构试题1参考答案

一、1——5：DADAB 6——10：CCBDD

二、1——5：ⅹ√ⅹⅹ√ 6——10：√ⅹⅹⅹⅹ

三、 1、①f→prior， ②p→next→prior 2、10 15 12 3、顺序压缩 4、2(n-1)

5、129 6、n/2的最小整数 7、(p→lchild==NULL)&&(p→rchild==NULL) 8、0 9、n(n-1) 10、归并排序

四、1、 答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。双链表 的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。

2、答案：（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余 数法的模，则可得其散列函数为h(k)=k。

（2）若用线性探测法解决冲突，则可构造出散列表如下： 13 14 35 17 29 153 0 1 2 3 4 5 6 7 8 9 10 11

此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表为：

3、 答案：（1）无向图的邻接矩阵所有数值之和除以2，为边数。有向图邻接矩阵各行 数值之和为总边数。邻接表表示无向图内部顶点个数除以 2，有向图内部顶 点个数。

（2）无向图中 I 行和 J 列的交叉点的值是否为 1。有向图 I 行 J 列交叉点或 I列和 J行交叉点的值为1。

（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数 值之和。 4答案：

5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。

具有3个结点的二叉树的形态为：5种形态，有左右之分。

6：答案：

五、1、 答案： void exchange(Bin Tree T)

{ if(T)

{ if(!T→lchild&&T→rchild) {T→lchild= T→rchild; T→rchild=NULL; } exchange(T→lchild);

exchange(T→rchild); }}

2、 答案： int oddbefore(A,n)//将数组 A[0?n-1]中所有奇数移到所有偶数之前

int A[ ];

{ int c,i,j; i=0;j=n-1;//初始化 i、j while(i

{while((A[i]%2==1)&&(i

while((A[i]%2==0)&&(i

if(i

A[i]=A[j]; A[j]=c; i++; j--; } } return(1)

} //oddbefore

数据结构试题2 一、单项选择题（每小题3分，共30分） 1、下列排序算法中，（ ）排序在每趟结束后，不一定能选出一个元素放到其排好序的最终位置上。

A、选择 B、冒泡 C、归并 D、堆

2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 3、串的长度是（ ）。

A、串中不同字符的个数 B、串中不同字母的个数 C、串中所含字符的个数且字符个数大于 0 D、串中所含字符的个数

4、有一个散列表，表长度 m为 100，采用除余法构造散列函数，即 H(k)=k%P,(P 小于等于 m)，为使散列函数有较好的性能，P 的选择应是（ ）。 A、99 B、97 C、91 D、93

5、在包括 n个键值的二叉排序树中查找一个键值，其平均比较的量级为（ ）。

A、O(n) B、O(logn) C、O(nlogn) D、O(n)

6、对有14个元素的有序表 A[1?14]作二分查找，查找A[4]时的被比较元素依次为（ ）。

A、A[1]，A[2]，A[3]，A[4] B、A[1]，A[14]，A[7]，A[4] C、A[7]，A[3]，A[5]，A[4] D、A[7]，A[5]，A[3]，A[4] 7、具有65个结点的完全二叉树其深度为（ ）。

A、8 B、7 C、6 D、5

8、带权有向图G用邻接矩阵 A存储，则顶点 i的入度等于 A中（ ）。

A、第 i行非无穷元素之和 B、第 i列非无穷元素之和

C、第 i行非零且非无穷元素个数 D、第 i列非零且非无穷元素个数 9、队列操作的原则是（ ）。

A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 10、若表R在排列前已按元素键值递增顺序排序，采用（ ）的比较次数少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 二、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１ 分，共１０分） 1、在栈空的情况下，不能做退栈运算，否则产生下溢。 （ ）

2、在快速排序算法中，取待排序的 n个记录中的第一个的键值为基准，将所有记 录分为两组，读记录就排在这两组的中间，这也是该记录的最终位置。 （ ）

3、在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使 用二分查找方法。 （ ） 4、设有键值序列（k1，k2，?，kn），当 i>n/2时，任何一个序列（k1，k2，?，kn）一定是堆。 （ ）

5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度h。

（ ）

6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。 （ ） 7、双循环链表中，任一结点的前驱指针均为不空。 （ ）

8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复 杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。 （ ）

9、如果有向图 G=(V，E)的拓扑序列不唯一，则图中必有两条弧和 存在。（ ）

10、矩阵压缩存储的方法是用三元组表存储矩阵元素。 （ ） 三、填空题（每小题2分，共20分）

1、设 sq[1?maxsize]为一个顺序存储的栈，变量 top 指示栈顶元素的位置。作进栈操作时，必须判别____。如要把栈顶元素取到 x中，需执行语句__ ___。 2、设一个二叉树共有50个叶结点（终端结点），则共有_______个度为2的结点。

3、在单链表中，若要在指针p所指结点(data，next)后插入指针s所指结点，则需要执行下列两条语句：s→next=p→next;_________。 4、3个结点可构成_________棵不同形状的树。

5、利用直接选择排序算法对 n个记录进行排序，最坏情况下，记录交换的次数为 _______ 6、如果含 n个顶点的图是一个环，则它有_________棵生成树。

7、如果要将序列{50，16，23，68，94，70，73}建成堆，则只需把 16 与______ 相互交换即可。 8、在一棵高度为 h 的平衡二叉树中，最少含有_________个结点，最多含有 2 h -1 个结点。 9、假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中，其中 B[0]存储矩阵中第1个元素a11，则B[31]中存放的元素是___________。 10、在单链表上难以实现的排序方法有___________和堆排序。 四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指 针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？

2、 一项工程由P1、 P2、 ?、 P6六项子工程组成， 这些工程之间有下列关系： P1

（2）求出在等概率情况下，查找成功的平均查找长度。

4、设下图所示的二叉树是由森林转化而成的，试将它还原为森林。

5、何为队列的“假溢出”现象？如何解决？ 6、分析以下程序段中语句x=x+y的执行次数。

x=0; y=0;

for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for(int k=1;k<=j;k++) x=x+y;

五、算法设计题（每题15分，共30分）

说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。 1、设计一个算法，求出指定结点在给定的二叉排序树中所在的层次。

2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于 min且小于 max的元素（若表中存在这样的元素）的算法。 数据结构试题2答案

一、1——5：CDDBB 6——10：CBDAA 二、1——5：√√√ⅹⅹ 6——10：ⅹ√ⅹⅹⅹ

三、1、① 栈是否满（或top=maxsize） ②x=sq[top] 2、49 3、p→next=s;

4、2 5、n-1 6、n 7、50 8、h 9、A82 10、快速排序 四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表

的删除时间复杂度为O(1)，单循环链表删除p结点的时间复杂度为O(n)。

2、答案：可给出有向图表示各子工程间的关系按照入度为零的结点先访问的原则，访问各

个结点即可。

找出3个可能的施工顺序如下：

P1，P2，P3，P4，P5，P6 P1，P4，P2，P3，P5，P6 P4，P5，P1，P2，P3，P6

3、答案：（1）：

（2）ASL=（1*7+2*4+3*1）/12=5。

4、答案：

5、答案：队列的“假溢出”现象是指用数组实现的顺序队列中，对尾指针已达到数组的下标上界产生上溢而对头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间首尾相连。

6、答案：

五、1、答案： int level(t,p)；

bitree *t,*p; { int count; count=0; if(t==NULL)

return(0);

else { count=count+1; while(t→data!=p→data) { if(t→data

t= t→rchild; else

t= t→lchild;

count=count+1; } } return(count); }

2、答案：delete(head,max,min) //删除有序单链表中所有值大于min且小于

max 的元素 linklist *head; int max,min;

{ linklist *p,*q;

if(head!=NULL) { q=head;

p=head→next; }

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

q→next=p; }

数据结构试题3 一、单项选择题（每小题3分，共30分）

1、假设有 n个关键字，它们具有相同的Hash 函数值，用线性探测法把这 n个关键字存入到Hash地址空间中要做（ ）次探测。

A、n2 B、n(n+1) C、n(n+1)/2 D、n(n-1)/2 2、若有一个栈的输入序列是 1，2，3，?，n 输出序列的第一个元素是 n，则第 i 个输出元素是（ ）。

A、n-i B、n-i-1 C、n-i+1 D、不确定 3、在一棵度为3的树中，度为 3的结点数为 2 个，度为2的结点数为 1个，度为1 的结点树为2个，那么度为 0的结点数为（ ）。

A、4 B、5 C、6 D、7 4、在一个具有 n个结点的无向完全图中，包含有（ ）条边。

A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n2

5、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，需（ ）次比较可检索成功。

A、 1 B、2 C、3 D、4 6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（ ）。

A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接选择排序 7、已知 8 个元素（34，76，45，18，36，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（ ）。

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

8、设有一个10阶的对称矩阵 A，采用压缩存储方式以行序为主存储，a00为第一个元素， 其存储地址为0，每个元素占有 1个存储地址空间，则a85的地址为 （ ）。

A、13 B、33 C、17 D、32 9、设关键字序列为：3，7，6，9，8，1，4，5，2。进行排序的最小交换次数为

（ ）。

A、6 B、7 C、8 D、20 10、给定权的集合{15，3，14，2，6，9，16，17}，所构造出的哈夫曼树的带

权路径长度为（ ）。

A、129 B、219 C、189 D、229 二、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分，

共１０分）

1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 （ ）

2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。 （ ）

3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。 （ ） 4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突 的方法两个方面。 （ ） 5、因为算法和程序没有区别，所以在数据结构中二者是通用的。 （ ） 6、进栈操作 push(x,s)作用于链接栈时，无须判满。 （ ） 7、稳定排序算法是最好的。 （ ） 8、二叉搜索树的左、右子树都是二叉搜索树。 （ ）

9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。 （ ） 10、表中的每一个元素都有一个前驱和后继元素。 （ ） 三、填空题（每小题2分，共20分）

1、在散列表(Hash)查找中，评判一个散列函数优劣的两个主要条件是_______和________。

2、设根结点处在第一层，那么具有 n 个结点的完全二叉树，其高度为_____。 3、快速排序方法的最坏时间复杂度为______，平均时间复杂度为___。 4、给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为_________。

5、设图 G 的顶点数为 n，边数为 e，各顶点的度数为 D(Vi)，则e=________。 6、将5个不同的数据进行排序，至少需要比较_____次，至多需要比较_______次。

7、二分折半查找的查找速度一般比顺序查找的速度快，设有100个元素，用二分折半查找时，最大比较次数是____，最小比较次数是_____。 8、由 a，b，c3 个结点构成的二叉树，共有_________种不同的结构。 9、在一棵高度为 h 的平衡二叉树中，至少含有________个结点，最多含有 2 h -1 个结点。

10、在一个单链表中删除*p 结点，应执行如下操作 ：

q=p→next;

p→data=p→next→data; p→next=________; free(q);

四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？ 2、假设用于通讯的电文仅有 8 个字母组成，字母在电文中出现的频率分别为：7， 19，2，6，32，3，21，10。试用这8个频率值构造哈夫曼树，并画出该哈夫曼所对应的森林。

3、已知一个长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec）： （1）构造最价二叉排序树；

(2)试求在等概率情况下对此二叉排序树进行折半检索时检索成功的平均长度。

4、对于下图，试给出：

（1）每个顶点的入度和出度； （2）邻接矩阵； （3）逆邻接表； （4）强连通分量；

5、快速排序、插入排序、自然两路归并排序、堆排序，哪一种排序方法所需的辅助空间最大？请简单说明。

6、分析以下程序段中语句x=x+y的执行次数。

x=0; y=0;

for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for(int k=1;k<=j;k++) x=x+y;

五、算法设计题（每题15分，共30分）

说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。 1、假设以二叉链表作为二叉树存储结构，其类型定义如下：

typedef struct node { char data;

五、1、算法的 ADL描述如下：

算法DEL(list,i) q←list

IF (I=1) THEN

list←next(list) ELSE

{ FOR j=1 TO i-1 DO { r←q q←next(q)

IF (q=NULL) THEN

{ PRINT(“链表中不存在第 i个结点”) RETURN } }

next(r)←next(q)6 } DELETE q

算法的时间复杂度为O(n)

2．假设邻接矩阵为 adjacency （二维数组）， 顶点的度保存在一维数组A中。

算法的ADL描述如下： [初始化]

FOR i=1 TO n DO A[i]←0

FOR i=1 TO n DO FOR j=1TO n DO

IF adjacency[i,j]=1 THEN A[i]←A[i]+1

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