数据结构试卷一 一、单项选择题（每小题3分，共30分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时(). A.仅修改头指针 B.头、尾指针都要修改 C.仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( A.队列 B.栈 C.线性表 D.二叉树 4.数据结构中，与所使用的计算机无关的是数据的()结构。 A.逻辑 B.物理 C.存储 D.逻辑与物理 5.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。 则原顺序表的长度为()。 A.21 B.20 C.19 D.25 6.元素2,4,6按顺序依次进栈，则该栈的不可能的输出序列是()。 A.642B.624 C.426 D.264 7.一个队列的入队序列是5,6,7,8，则队列的输出序列是()。 A.5678 B.8765 C.7865 D.可能有多种情况 8.串函数StrCmp(“d”,“D”)的值为()。 A.0 B.1 C.-1 D.3 9.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点 的直接后继，现要删除q所指结点，可用语句()。 A.p=g今next B.p→next=qC.p→next=q→next D.q→next=NULL 10.设一棵哈夫曼树共有n个非叶结点，则该树一共有()个结点。 A.2*n-1 B.2*知+1 C.2*知 D.2*(n-1) 二、填空题（每空2分，共24分) 1.通常从四个方面评价算法的质量： 2.根据数据元素间关系的不同特性，通常可分为 四类基本结构。 3.在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为 (结点的指针域为next) 4. 遍历二叉排序树可得到一个有序序列。 5.数据的物理结构主要包括 和 两种情况。 三、综合题（每小题10分，共30分） 1.在如下数组A中链接存储了一个线性表，表头指针为A[O]next,试写出该线性表。 A0123456 7
1 数据结构试卷一 一、单项选择题（每小题 3 分，共 30 分） 1. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 5.在一个长度为 n 的顺序表中为了删除第 5 个元素，从前到后依次移动了 15 个元素。 则原顺序表的长度为（ ）。 A. 21 B. 20 C. 19 D. 25 6.元素 2，4，6 按顺序依次进栈，则该栈的不可能的输出序列是（ ）。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 7.一个队列的入队序列是 5，6，7，8，则队列的输出序列是（ ）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 8.串函数 StrCmp（“d”，“D”）的值为（ ）。 A．0 B．1 C．-1 D．3 9．在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点 的直接后继，现要删除 q 所指结点，可用语句（ ）。 A．p=q→next B．p→next=q C．p→next=q→next D．q→next=NULL 10.设一棵哈夫曼树共有 n 个非叶结点，则该树一共有（ ）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 二、填空题（每空 2 分，共 24 分） 1. 通常从四个方面评价算法的质量：_________、_________、_______和________。 2．根据数据元素间关系的不同特性，通常可分为________、________、________、 ________四类基本结构。 3．在一个链队中，设 f 和 r 分别为队头和队尾指针，则删除一个结点的操作为________。 (结点的指针域为 next) 4.________遍历二叉排序树可得到一个有序序列。 5.数据的物理结构主要包括_____________和______________两种情况。 三、综合题（每小题 10 分，共 30 分） 1．在如下数组 A 中链接存储了一个线性表，表头指针为 A [0].next，试写出该线性表。 A 0 1 2 3 4 5 6 7
data 6050789034 40 next 3 5 7 2 0 4 1 A0]A[3]A[2]A[7JA[1]A[5]A[4]A[O] 2.请画出下图的邻接矩阵。 3.设一组初始记录关键字序列为(45,80,48,40,22,78)，则分别给出第4趟简单 选择排序和第4趟直接插入排序后的结果。 四、程序填空题（每空2分，共16分） 1.以下冒泡法程序对存放在a[1],a[2],…,a[n]中的序列进行冒泡排序，完成程 序中的空格部分，其中n是元素个数，程序按升序排列。 Void bsort (NODE a[]int) NODE temp; int i,j,flag; for(j=1;(1) :j++): {f1ag=0; for(i=1;(2) :i++) if(a[i].key>a[i+1].key) {f1ag=1: temp=a[i]; (3) (4) } if(flag==0)break; 程序中f1ag的功能是(5) 7.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right,数据域为data,其数据类型为字符型，BT指向根结点)。 Void Postorder(struct BTree Node *BT) if(BTI=NULL) (1) (2) (3) 2
2 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 A[0] A[3] A[2] A[7] A[1] A[5] A[4] A[0] 2．请画出下图的邻接矩阵。 3．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第 4 趟简单 选择排序和第 4 趟直接插入排序后的结果。 四、程序填空题（每空 2 分，共 16 分） 1．以下冒泡法程序对存放在 a[1]，a[2]，……，a[n]中的序列进行冒泡排序，完成程 序中的空格部分，其中 n 是元素个数，程序按升序排列。 Void bsort (NODE a[ ], int) { NODE temp; int i,j,flag; for(j=1; （1） ;j++); {flag=0; for(i=1; （2） ;i++) if(a[i].key>a[i+1].key) {flag=1; temp=a[i]; （3） ; （4） ; } if(flag= =0)break; } } 程序中 flag 的功能是（5） 7．以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为 left 和 right，数据域为 data，其数据类型为字符型，BT 指向根结点）。 Void Postorder (struct BTree Node *BT) { if(BT!=NULL){ （1） ; （2） ; （3） ; }
} 试题答案； 一、单项选择题（每小题3分，共30分） 1-5.A DD A B 6-10.BA CC B 三、填空题（每空2分，共24分） 1.正确性、易读性、强壮性、高效率 2.集合、线性、树形、图状 3.f=f->next; 4.中序 5.顺序存储结构、链式存储结构 三、综合题（每小题10分，共30分） 1.线性表为：(78,50,40,60,34,90) 2. 「01110 10101 11011 10101 邻接矩阵： 01110 3.(22,40,45,48,80,78),(40,45,48,80,22,78) 四、程序填空题（每空2分，共16分） y (1)j=n-1 (2)ileft) (2)Postorder(BT>right) (3)printf(“%c”,BT→data)
3 } 试题答案； 一、单项选择题（每小题 3 分，共 30 分） 1-5．A D D A B 6-10．B A C C B 三、填空题（每空 2 分，共 24 分） 1. 正确性、易读性、强壮性、高效率 2.集合、线性、树形、图状 3. f=f->next; 4.中序 5.顺序存储结构、链式存储结构 三、综合题（每小题 10 分，共 30 分） 1．线性表为：（78，50，40，60，34，90） 2． 邻接矩阵： 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 3．(22，40，45，48，80，78)，(40，45，48，80，22，78) 四、程序填空题（每空 2 分，共 16 分） 1． （1）j<=n-1 （2）i<=n-j （3）a[i]=a[i+1] （4）a[i+1]=temp （5）当某趟冒泡中没有出现交换则已排好序，结束循环 2． （1） Postorder(BT→left) （2）Postorder(BT→right) （3） printf(“%c”,BT→data)