《绵职院计科系计应班软件班数据结构期末试卷001b1》由会员分享，可在线阅读，更多相关《绵职院计科系计应班软件班数据结构期末试卷001b1（6页珍藏版）》请在金锄头文库上搜索。
1、一、选择题：一、选择题：(151 分)1. 下面有关链队列的描述正确的是（） 。 A. 链队列只需要一个指向队头的指针 B队尾结点的指针域为空表示队列空 C. 入队一个元素实际上是建立一个新的尾结点 D出队一个元素实际上是从队尾删除一个结点2. 设栈 S 和队列 Q 的初始状态为空，元素 1, 2, 3, 4, 5, 6 依次通过栈 S，一 个元素出栈后进入队列 Q ，若 6 个元素出队的顺序是 2, 4， 3, 6, 5, 1 则栈 S 的容量至少是（） 。 A. 6 B. 4 C . 3 D. 23. 由 3 个结点可以构造出（）种不同的二叉树： A. 2 B. 3 C. 4 D. 54.
2、 在下列排序方法中，哪一个是稳定的排序方法（ ） 。 A直接选择排序 B二分法插入排序 C希尔排序 D快速排序5. 对 n 个记录的序列进行快速排序，所需的辅助存储器空间为( )。 A.0(1) B.0(logn) C.0(n) D.0(n2)6. 深度为 6 的二叉树至多有结点数为( )。 A. 11 B65 C. 63 D137. 下面关于串的叙述中，哪一个是不正确的（ ） 。 A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要的运算 D串既是可采用顺序存贮，也可采用链式存贮8. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺 序 A都不相同 B.
3、完全相同 C先序和中序相同而后序不同 D. 中序和后序相同而先序不同9. 在堆排序中，当初堆建成后，该堆根的记录必是（ ） 。 A.文件中的第一个记录 B.文件中具有最大（或最小）关键字的记录B 卷 第 2 页 共 7 页C.文件中的一个记录 D.文件中的最后一个记录10.下面有向图可以排成不同的拓扑序列，其中正确的序列为（ ） 。A、a c b d B、a d b c C、a b c d D、b a d c11. 树形结构中，每个结点（ ） A、无直接前驱 B、可有多个直接前驱 C、至多只能有一个直接前驱 D、有三个以上的直接前驱12. 一个深度为 4 的完全二叉树中序号为 13 的结点的_
4、。 A. 双亲结点序号为 6 B. 左孩子结点序号为 26 C右孩子结点序号为 27 D双亲结点序号为 713. 对于一个有 n 个元素的线性表，采用顺序存储结构，若要删除第 i 个结点， 需要移动元素的个数有_个。 A.1 B. n C. n-i D.i14. 下面关于数据结构的描述不正确的是_。 A数据结构包括的内容是数据的逻辑结构、数据的存储结构、数据运算。 B数据的逻辑结构是指数据及其数据的逻辑关系。 C数据的存储结构是指数据在计算机中的表示。 D数据的运算是指对数据施加的操作。15. 一棵二叉树结点的先根遍历序列为 ABCD，中根遍历序列为 CBAD，则其后根遍 历序列为_。 ABC
5、DA B CBDA C BCAD D以上都不对二、填空二、填空：(53 分+35 分)装 订. 线数据结构B 卷 第 3 页 共 7 页1. 设有二维数组 A09，019其中每个元素占两个字节。数组按列优先顺序 存贮。第一个元素的存贮地址为 100。则元素 A6，6的存贮地址为 _.2. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列 一致） ，则这棵二叉树必定是_。3. 对于有 n 个顶点的连通图，至少有_条边。由此而构成的生成树有_条边。 有_条边的无向图为完全图。4. 设有一个用线性探测法解决冲突得到的 Hash 表（Hash 函数为 H(k)=K Mod 11）有一
6、组数（13,25,80,16,17,14,4） ，则探测元素 14 的地址值为( ) （填入上 Hash 表中）5. 单链表 H 的结点在逻辑_（有序/无序） ，在物理上是_有序/无序） 。以下是算法填空 6. 下列函数的功能是：对给定的不带头结点的单链表进行逆置，即原线性表(a1, a2,an+1,an) 逆置后变成(an,an-1,a2,a1)。单链表类型定义如下：struct link_node int data; struct link_node *next; ; struct link_node *revers(struct link_node h) /* h 为单链表的头指针，函数
7、返回逆置后的单链表头指针 */ struct link_node *s,*p,*q; qNULL; ph; while(p) s=p-next; _;q=p; p=s; 装 订. 线B 卷 第 4 页 共 7 页 h=q; return(h); 7. 下列函数的功能是：实现链式队列的入队操作。其中链式队列的定义如下： typedef struct queue_node int data; struct queue_node *next; QUEUE_NODE; typedet struct queue QUEUE_NODE *front, *tail; QUEUE; void in_like
8、queue(QUEUE q, int key) /* q 为链式队列，并且带头结点，key 为将要入队的内容 */ QUEUE_NODE *s; s=(QUEUE_NODE*)malloc(sizeof(QUEUE_NODE); s-data=key; s-next=NULL; _; )8. 下列递归函数的功能是：中序输出给定的二叉树结点。其中二叉树中的结点 类型定义如下： typedef bin_tree_node int data; bin_tree_node *llink, *rlink; BIN_TREE; void inorder(BIN_TREE *tree) if(tree) _
9、; printf(“%d “, tree-data); inorder(tree-rlink); 三、简答题：三、简答题：(40 分)装 订. 线数据结构B 卷 第 5 页 共 7 页1. 设电文中出现字字母 A,B,C,D,每个字母在电文中出现的次数分别是 2,7,4,5 按哈夫曼编码求 A,B,C,D 的编码,请作出哈夫曼树.并求 WPL.2. 己知如图所示的一棵树，画出其双亲表示法的存储结构图, 并将此树的转化 为二叉树。3.对于如下带全的有向图写出邻结表；并用 C 语言描述起存储结构。 （将其结构 填充完整）#define MAX typedef struct ArcNode ArcN
10、ode; /边 typedef struct Vnode Vnode,AdjlistMAX; /结点 typedfe stru int kind /图的种B 卷 第 6 页 共 7 页类标志 ALGrph /图4. 求图中 o 点到 c 的最短路径（描述过程）四、算法设计四、算法设计(15 分)带有头指针 head 的单链表中，存放着 n 个整数，现从单链表中删除数值为 key 的结点。编写一个子函数 delete，描述该算法；若完成删除，则返回 OK否则返回 ERROR、其中数据类型和子函数说明用类 C 语 言描述为： #define NULL 0 /* 空指针 */ #define OK 1 #define ERROR 0 typedef struct node /* 结点类型 */ int data; /* 数据域 */ struct node *next; /* 指针域 */ *list; int key; int delete(list head, int key); /* 子函数说明 装 订. 线
