计算机考研数据结构试卷十二（练习题含答案）

共25套适用于计算机考研数据结构系统练习

（PS：其他正在整理，敬请期待）

数据结构试卷12

一、填空题

1.已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。

2.在有n个结点的无向图中，其边数最多为_______。

3.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。

4.对矩阵采用压缩存储是为了___ ____。 5.带头结点的双循环链表L为空表的条件是_______。

6.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是 。

7. 对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。

8.在双向链表中，每个结点有两个指针域，一个指向____ __，另一个指向_ __ __。

9.由一棵二叉树的前序序列和 可唯一确定这棵二叉树。 10.折半查找的存储结构仅限于___ _，且是_ ___。

二、 选择题

1.对n个记录的文件进行快速排序，所需要的辅助存储空间为【 】。

A O（1） B O（log2n） C O（n） D O（n2） 2.哈夫曼树中一定不存在【 】。

A 度为0的结点B 度为1的结点 C 度为2的结点 D 带权的结点 3.下述哪一条是顺序存储方式的优点？【 】

A 存储密度大 B 插入和删除运算方便 C 获取符合某种条件的元素方便 D 查找运算速度快

4.有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）【 】。

A 658 B 648 C 633 D 653 5.列关于二叉树遍历的叙述中，正确的是【 】。

A 若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点

B 若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点

C 若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点

D 若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的

中序遍历最后一个结点

6.层二叉树的结点总数最多为【 】。

A 2k-1 B 2k+1 C 2K-1 D 2k-1 7.线性表进行二分法查找，其前提条件是【 】。

A 线性表以链接方式存储，并且按关键码值排好序

B 线性表以顺序方式存储，并且按关键码值的检索频率排好序 C 线性表以顺序方式存储，并且按关键码值排好序

D 线性表以链接方式存储，并且按关键码值的检索频率排好序 8.n个记录进行堆排序，所需要的辅助存储空间为【 】。

A O(1og2n) B O(n) C O(1) D O(n2)

9.线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有【 】个。

A 1 B 2 C 3 D 4 10.列关于数据结构的叙述中，正确的是【 】。

A 数组是不同类型值的集合

B 递归算法的程序结构比迭代算法的程序结构更为精炼 C 树是一种线性结构

D 用一维数组存储一棵完全二叉树是有效的存储方法

三、 计算与算法应用题：

1.画出下列树对应的二叉树，并写出其先根遍历序列：

A B C D F E G

2.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。

四、阅读下列算法，分析其作用

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

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

const 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 <

该算法的输出结果为：_________________________________.

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); } }

该算法的功能是：___________________________ 五、算法设计

1.试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。 2.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。

Head d e ^ a c b

答案

一、 填空

1、 1225 2、 n(n-1)/2 3、 head(A)

4、 节省空间

5、 L->next=L->prior 或 L->next=L 6、 1044

7、 入栈（插入） ， 出栈（删除） 8、 前驱结点 ， 后继结点 9、 中序序列 10、 顺序存储结构 ， 有序的

二、 选择

1-5 BBADA 6-10 ACCDD

三、 计算与算法应用题

画出下列树对应的二叉树，并写出其先根遍历序列：

B A 先根遍历序列： A B D E G F C

D C

E

F G

4.将关键字序列为{54，29，37，86，71，91，8，31，44，26}进行归并排序，写出各趟详细过程。

54 29 37 86 71 91 8 31 44 26

29 54 37 86 71 91 8 31 26 44

29 37 54 86 8 31 71 91 26 44

8 29 31 37 54 71 86 91 26 44

8 26 29 31 37 44 54 71 86 91

四、阅读下列算法，分析它的作用

1. 该算法的输入结果是：34 91 30 45 63 78

2. 该算法的功能是：交换二叉树的左右子树的递归算法。

五、算法设计题：

1. 对于排列的解空间可构造一个虚拟的解空间树，比如n=5，k=3时的解空间树如下图所示，可采用对此树进行先序遍历方式进行遍历，并用递归法进行递归输出从n个数中挑选 k个进行排列所得序列。

具体算法实现如下：

// 文件路径名:exam7\\alg.h template

void Arrage(ElemType a[],int k,int n, int outlen=0)

// 操作结果: 回溯法输出排列序列，a[0..k-1]为k个数的排列序列outlen为当前所求排列 // 序列的长度，其中outlen=k时的排列序列为所求；n为list数组长度 { if (k < 0 || k >= n) return; // 此时无排列 int i; // 临时变量 if (outlen == k + 1) { // 得到一个排列 for (i = 0; i < k; i++) { // 输出一个排列 cout << a[i]; // 输出a[i] } cout << \ \ // 用空格分隔不同排列 } else { // 对解空间进行前序遍历，a[outlen..n]有多个排列，递归的生成排列 for (i = outlen; i < n; i++) { // 处理a[i] Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] Arrage(a, k, n, outlen + 1); // 对序列长度outlen+1递归 Swap(a[outlen+1], a[i]); // 交换a[outlen+1]与a[i] } } }

2.编写一个算法，交换单链表中p所指向的结点和其后续结点的两个结点，Head指向该链表的表头，P指向链表中的某一结点。

Head

a bd c e ^

void Link ::swap( NodeType *p) //0.5分 { NodeType *q,*r,*s;

q=p->next; //0.5分 if(q!=NULL) //1分 { if(p==Head) //4分 {Head=Head->next; s=Head->next; Head->next=p; p->next=s; }

Else // 4分 { r=Head;

while(r->next!=p) r=r->next; r->next=q;

p->next=q->next; q->next=p; } } }

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