<4D F736F F D E3131CAFDBEDDBDE1B9B9C6DAD6D0BFBCCAD4A3A8BAACB2CEBFBCB4F0B0B8A3A92E646F63>

Size: px

Start display at page:

Download "<4D F736F F D E3131CAFDBEDDBDE1B9B9C6DAD6D0BFBCCAD4A3A8BAACB2CEBFBCB4F0B0B8A3A92E646F63>"

铅粗可
7 years ago
Views:

1 一选择题 ( 每小题 2 分, 共 30 分, 奇偶 ) 1. 从逻辑上可以把数据结构分为 ( ) 两大类. 动态结构静态结构. 顺序结构链式结构. 线性结构非线性结构 D. 初等结构构造型结构 2. 下面关于线性表的叙述中, 错误的是哪一个?( ). 线性表采用顺序存储, 必须占用一片连续的存储单元. 线性表采用顺序存储, 便于进行插入和删除操作. 线性表采用链接存储, 不必占用一片连续的存储单元 D. 线性表采用链接存储, 便于插入和删除操作 3. 对于顺序存储的线性表, 访问结点和增加删除结点的时间复杂度为 ( ).O(n) O(n). O(n) O(1). O(1) O(n) D. O(1) O(1) 4. 线性表 ( a1,a2,,an) 以链接方式存储时, 访问第 i 位置元素的时间复杂性为 ( ).O(i).O(1).O(n) D.O(i-1) 5. 如果最常用的操作是取第 i 个结点及其前驱, 则采用 ( ) 存储方式最节省时间 D. 单链表. 双链表. 单循环链表 D. 顺序表 6. 对于一个头指针为 head 的带头结点的单链表, 判定该表为空表的条件是 ( ).head==null.head next==null.head next==head D.head!=NULL 7. 有六个元素 6,5,4,3,2,1 的顺序进栈, 问下列哪一个不是合法的出栈序列?( ) D 一个栈的输入序列为 , 则下列序列中不可能是栈的输出序列的是 ( ) D 经过以下栈运算后,x 的值是 ( ) InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x);.a.b.1 D 输入序列为, 输出为时 ( 假设元素出栈则输出 ), 经过的栈操作为 ( ).push,pop,push,pop,push,pop.push,push,push,pop,pop,pop.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop 11. 一个队列的入队序列为 1234, 则队列可能的输出序列是 ( ) D 用一个大小为 6 的数组来实现循环队列, 且当前 rear 和 front 的值分别为 0 和 3, 当从队列中删除一个元素, 再加入两个元素后,rear 和 front 的值分别为多少?( ). 1 和 5. 2 和 4. 4 和 2 D. 5 和若循环队列用数组 [0,m-1] 存放元素, 其头尾指针分别为 front 和 rear, 则当前队列的长度是 ( ). (rear-front+m)%m. rear-front+1. rear-front-1 D. (rear-front)%m 14. 循环队列存储在数组 [0..m] 中, 则入队时的操作为 ( ) D. rear=rear+1. rear=(rear+1) mod (m-1). rear=(rear+1) mod m D. rear=(rear+1) mod (m+1) 15. 设计一个判别表达式中左, 右括号是否配对出现的算法, 采用 ( ) 数据结构最佳 D. 线性表的顺序存储结构. 队列. 线性表的链式存储结构 D. 栈 16. 串的长度是指 ( ). 串中所含不同字母的个数. 串中所含字符的个数. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 1

2 17. 数组 [0..5,0..6] 的每个元素占五个字节, 将其按列优先次序存储在起始地址为 1000 的内存单元中, 则元素 [5,5] 的地址是 ( ) D 设有数组 [i,j], 数组的每个元素长度为 3 字节,i 值为 1 到 8,j 值为 1 到 10, 数组从内存首地址开始顺序存放, 当用以列为主存放时, 元素 [5,8] 的存储地址为 ( ) D 模式串 t= abcaabbcabcaabdab, 该模式串的 next 数组的值为 ( ) D D 串 "ababaaababaa" 的 next 数组为 ( ) D 以下哪个数据结构, 是非线性数据结构 ( ). 树. 字符串. 队列 D. 栈 22. 在下述结论中, 正确的是 ( ) D 1 只有一个结点的二叉树的度为 0;2 二叉树的度为 2; 3 二叉树的左右子树可任意交换 ; 4 深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树 D 深度为 5 的二叉树至多有 ( ) 个结点 D 二叉树的第 k 层上最多含有结点数为 ( ).2 k.2 k k-1 D.2 k 一棵完全二叉树上有 1001 个结点, 其中叶子结点的个数是 ( ) D D 一棵具有 n 个结点的完全二叉树的树高度 ( 深度 ) 是 ( ). logn +1.logn+1. logn D.logn 已知一棵二叉树的前序遍历结果为 DEF, 中序遍历结果为 EDF, 则后序遍历的结果为 ( ).EFD.FED.EDF D. 不定 28. 若算术表达式的中缀形式为 +*-D/E, 后缀形式为 *+DE/-, 则其前缀形式为 ( ) D.-+*/DE. -+*D/E.-+*/DE D. -+*/DE 29. 根据使用频率为 5 个字符设计的哈夫曼编码不可能是 ( ) D.000,001,010,011,1.0000,0001,001,01,1.000,001,01,10,11 D.00,100,101,110, 设给定权值总数有 n 个, 其哈夫曼树的结点总数为 ( ) D. 不确定.2n.2n+1 D.2n-1 二是非判断题 ( 每小题 1 分, 共 7 分, 奇偶 ) 1. 数据的物理结构是指数据在计算机内的实际存储形式 ( )T 2. 顺序存储方式的优点是存储密度大, 且插入删除运算效率高 ( ) 3. 线性表的特点是每个元素都有一个前驱和一个后继 ( ) 4. 线性表只能用顺序存储结构实现 ( ) 5. 循环队列通常用指针来实现队列的头尾相接 ( ) 2

3 6. 队列和栈都是运算受限的线性表, 只允许在表的两端进行运算 ( ) 7. 串是一种数据对象和操作都特殊的线性表 ( )T 8. 给定一棵树, 可以找到唯一的一棵二叉树与之对应 ( )T 9. 对一棵二叉树进行层次遍历时, 应借助于一个栈 ( ) 10. 由一棵二叉树的前序序列和后序序列可以唯一确定它 ( ) 11. 二叉树只能用二叉链表表示 ( ) 12. 在二叉树的第 i 层上至少有 2 i-1 个结点 (i>=1) ( ) 13. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和 ( ) 14. 哈夫曼树是带权路径长度最短的树, 路径上权值较大的结点离根较近 ( )T 三填空 ( 每空 2 分, 共 12 分, 必做题,1,2 小题每空只填一个语句 ) 1. 在带头结点的单链表 L 中删除第 i 个元素, 并由 e 返回删除元素的值 typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList; Status ListDelete_L(LinkList &L, int i, ElemType &e) int j = 0; LNode *q; p = L; while((p->next) && (j < i - 1)) p = p->next; ++j; if(!(p->next) (j > i 1))return ERROR; // 删除位置不合理 q = p->next; 1 e = q->data; free(q); return OK; 2.Search_in 函数, 实现在一个递增有序数组 ST 中采用折半查找法确定元素位置的算法 int Search_in(int *ST,int n,int key) /* 在有序表 ST 中折半查找其关键字等于 key 的数据元素若找到, 则函数值为该元素在表中的位置, 否则为 -1 n 为有序表的长度 */ int low,high,mid; low = 1; /* 置区间初值 */ high = n; while(low <= high) 3

4 mid = 2 if (key==st[mid]) return mid; else if 3 high=mid-1; else 4 return -1; /* 顺序表中不存在待查元素 */ 参考答案 1 p->next = q->next; 2 (low + high)/2 ; 3 (key < ST[mid] ) 4 low = mid + 1; 3. 写出下列程序段的输出结果 ( 栈的元素类型 SElemType 为 char) void main() Stack S; char x,y; InitStack(S); x= c ; y= k ; Push(S,x); Push(S, a ); Push(S,y); Pop(S,x); Push(S, t ); Push(S,x); Pop(S,x); Push(S, s ); while(!stackempty(s)) Pop(S,y); printf(y); printf(x); 解 :stack 4. 写出以下程序段的输出结果 ( 队列中的元素类型 QElemType 为 char) void main() Queue Q; InitQueue(Q); char x= e, y= c ; EnQueue(Q, h ); EnQueue(Q, r ); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, a ); While(!QueueEmpty(Q)) DeQueue(Q,y); 4

5 cout<<y; cout<<x; 解 :char 四应用题 ( 每题 8 分, 共 40 分, 前 8 题奇偶, 第 9 10 题任选一题 ) 1. 由二叉树的中序序列及前序序列能唯一的建立二叉树, 试问中序序列及后序序列是否也能唯一的建立二叉树, 若不能则说明理由 ; 若能对中序序列 DEFG 和后序序列 DEGF 构造二叉树, 请 (1) 画出该二叉树 ;(2) 写出该二叉树的先序遍历序列 ;(3) 将该二叉树转换成对应的树 ( 或森林 ) 参考答案 : D E F G 2. 设一棵二叉树的先序中序遍历序列分别为 : 先序遍历序列 : D F E G H 中序遍历序列 : F D G E H (1) 画出这棵二叉树 (2) 写出这颗二叉树的后序遍历序列 (3) 将这棵二叉树转换成对应的树 ( 或森林 ) 参考答案 :(1) D E F G H (2) 后序序列 :FDGHE (3) 转换成森林 : E D E H D E D G H F G 5 F G H F

6 3. 二叉树可采用静态链表的形式表示, 即用游标指示器指示其后继结点在结构数组中的相对位置 ( 即数组下标 ), 游标为 0 相当于 NULL 指针设二叉树 T 的存储结构如下 : 其中 T 为树根结点的指针, 其游标值为 6,Lchild,Rchild 分别为结点的左右孩子的游标域,data 为结点的数据域完成下列各题 : (l) 画出该二叉树 T; (2) 写出按先序中序后序遍历该二叉树所得到的结点序列 D E F G H I 参考答案 : 先序 :EDFHGIJ 中序 :EHFDJIG 后序 :EHFJIGD J 4. 已知一组元素为 ( 45,62,25,78,81,36,47,79 ), 画出按元素排列顺序输入生成的一棵二叉排序树写出按先序中序后序遍历该二叉树所得到的结点序列参考答案 : 45,62,25,78,81,36,47,79 45 / \ \ / \ \ 81 / 79 6

7 先序 :45,25,36,62,47,78,81,79 中序 :25,36,45,47,62,78,79,81 后序 :36,25, 47,79,81,78,62, 设有正文 DDD, 字符集为,,,D, 利用赫夫曼算法设计一套二进制编码, 请画出赫夫曼树并给出每个字符的赫夫曼编码, 并说明这种编码的优点参考答案 : 字符,,,D 出现的次数为 9,1,5,3 其哈夫曼编码如下 :1,:000,:01,D:001 按左分支为 0, 右分支为 1 即可写出各字母的编码编码的优点是 : 为前缀编码, 不会产生歧义, 另外可以使编码最短 6. 给定一组数列 (15,8,10,21,6,19,3) 分别代表字符,,,D,E,F,G 出现的频度, 试叙述建立哈夫曼树的算法思想, 画出哈夫曼树, 给出各字符的编码值, 并说明这种编码的优点参考答案 : 哈夫曼树如下图 : 其中左右结点互换位置也正确但结点结合的顺序是唯一的 F D G E 按左分支为 0, 右分支为 1 即可写出各字母的编码编码的优点是 : 为前缀编码, 不会产生歧义, 另外可以使编码最短 7. 已知一棵二叉树的先序遍历序列为 D#E##FG####H##, 其中 # 表示空树, 请画出对应的二叉树将这棵二叉树转换成对应的树 ( 或森林 ) 参考答案 : / \ / \ \ D F H \ / E G 7

8 8. 已知含有 8 个结点的一棵二叉树, 按先序中序后序进行遍历后, 有些结点序号不清楚如下所示要求填写下列空白序号, 并构造出一棵符合条件的二叉树将这棵二叉树转换成对应的树 ( 或森林 ) 先根序遍历 _ 2 3 _ 5 _ 7 8 中根序遍历 3 _ 4 1 _ 后根序遍历 _ 参考答案 : 先根序遍历中根序遍历后根序遍历举例说明顺序队的假溢出现象, 简要叙述循环队列的数据结构, 并说明判定循环队列的队空条件和队满条件参考答案 :( 在队列的一端进入插入时,TOP 值会增加, 在另一端删除, 当判断 TOP==MX-1 为是, 这说明队已满但实际在队列的另一端还是有存储空间的, 这就是假溢出 ) 当 front 0,rear=M 时, 再有元素入队发生溢出, 称之为假溢出, 存储空间还有剩余为了改进这种状况, 可以将顺序队列想象为一个首尾相接的环状空间, 称之为循环队列假溢出现象和循环队列的数据结构基本上描述清楚就 OK 其中 : 循环队列的队空条件 :front == rear 队满条件 :(Q.rear+1) % MXQSIZE == Q.front 10. 已知下列字符 D E F G 的权值分别为 , 试填写出其对应哈夫曼树 HT 存储结构的终态, 即把下表填充完整 ( 生成的哈夫曼树权值左孩子小右孩子大, 权值相等时编号小的先取 ) weight parent lchild rchild 1 2 8

9 参考答案 : weight parent lchild rchild 五算法设计题 (10 分, 任选一题 ) 1. 编写算法, 将两个非递减有序顺序表和合并成一个新的非递减有序顺序表, 已知顺序表和的元素个数分别为 m 和 n 其中顺序表采用动态分配空间, 定义如下 : typedef struct ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 SqList; 参考答案 : void merge(sqlist, SqList, SqList &) int i = 0, j = 0, k = 0; while(i<.length && j <.length) If(.elem[i] <=.elem[j]).elem[k] =.elem[i]; i ++; k++; Else.elem[k] =.elem[i]; j ++; k++; While(i<.length).elem[k] =.elem[i]; i ++; k++; 9

10 While( j <.length).elem[k] =.elem[i]; j ++; k++;.length = k; 2. 假设二叉树采用二叉链表存储结构, 设计一个算法, 求中序遍历序列中第 k(1<=k<= 二叉树的结点个数 ) 个结点的值参考答案 : void InNode(iTree T, int k, int &n, TElemType &e)// 找到的结果存放在 e 中,n 初始为 0 if( T!= NULL) InNode( T->lchild, k, n, e); if( n >= k) return; n++; if(n == k) e = T->data; return; InNode(T->rchild, k, n, e); 3. 在一个递增的带头结点的单链表 L 中 ( 允许出现值域重复的结点 ), 设计一个函数删除值域重复的结点单链表带头结点, 其结点定义如下 : typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList; 参考答案 : void DeleteNode(LinkList &L) //L 为单链表的头结点指针 LinkList p = L->next; LinkList q; while(p->next!= NULL) if(p->data == p->next->data) 10

11 q = p->next; p->next = q->next; free(q); else p = p->next; 4. 假设二叉树 T 采用二叉链表存储结构, 设计一个算法, 计算该二叉树的高度其中二叉树的二叉链表表示定义如下 : typedef struct itnode TElemType data; struct itnode *lchild, *rchild; itnode, *itree; 参考答案 : int depth(itree T) int d = 0, d1,d2; if(t == NULL)retrun d; else d1 = depth(t->lchild); d2 = depth(t->rchild); if(d1 >= d2) d = 1 + d1; else d = 1 + d2; return d; 附加题 : 1 算法题编写算法, 顺序创建一个含有 n 个元素的带头结点的单链表 L 单链表存储结构定义如下 : typedef int ElemType; typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList; 测试样例格式说明 : [ 键盘输入 ] 第一行 : 单链表 L 的元素个数第二行 : 单链表 L 的各元素, 用空格分开 11

12 [ 正确输出 ] 第一行 : 单链表 L 的元素列表测试样例 : [ 键盘输入 ] [ 正确输出 ] 依次把结点 16,3,7,11,9,26,18,14,15 插入到初始状态为空的平衡二叉排序树中, 使得在每次插入后保持该树仍然是平衡二叉排序树要求画出每次插入后所形成的平衡二叉排序树 3. 线性表的顺序存储结构具有三个弱点 : 其一, 在作插入或删除操作时, 需移动大量元素 ; 其二, 由于难以估计, 必须预先分配较大的空间, 往往使存储空间不能得到充分利用 ; 其三, 表的容量难以扩充线性表的链式存储结构是否一定都能够克服上述三个弱点, 试讨论之 4. 已知模式串的 next 数组, 使用 KMP 算法进行串匹配, 以下空格应填入的语句是 () int Index_KMP(SString S, SString T, int pos) // 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置的 // KMP 算法其中,T 非空,1 pos StrLength(S) int next[255]; int i = pos; int j = 1; get_next(t, next); while (i <= S[0] && j <= T[0]) if (j == 0 S[i] == T[j]) // 继续比较后继字符 ++i; ++j; else ; // 模式串向右移动 if (j > T[0]) return i-t[0]; // 匹配成功 else return 0; // Index_KMP.j = next[j].i = next[j].j = i + 1 D.i = j n 阶对称矩阵, 将其上三角的元按列优先顺序压缩存放在一维数组 [1 n(n+1)/2] 中, 第一个元素 a1,1 存于 [1] 中, 则应存放到 [k] 中的元素 ai,j(1 <= i <= n,i <= j <= n) 的下标 i,j 与 k 的对应关系是 k=( ) D.i(i+1)/2 + j.i(i-1)/2 + j.j(j+1)/2 + i D.j(j-1)/2 + i 12

B 只有表尾指针而没有表头指针的循环单链表 C 非循环双链表 D 循环双链表 5 线性表 ( a1,a2,,an) 以链接方式存储时, 访问第 i 位置元素的时间复杂性为 ( ) A.O(i) B.O(1

B 只有表尾指针而没有表头指针的循环单链表 C 非循环双链表 D 循环双链表 5 线性表 ( a1,a2,,an) 以链接方式存储时, 访问第 i 位置元素的时间复杂性为 ( ) A.O(i) B.O(1 数据结构 2013 年春季期末复习提纲期末考试形式 : 闭卷试卷试卷题型 :1. 选择题 (20 分 ),2. 应用题 (30 分 )3. 程序填空题 (30 分 )4. 算法设计题 ( 20 分 ) 每章复习要点 : 第 1 章 : 概念理解 : 数据结构, 时间复杂度程序段 : i=1;