2022年大学数据结构考试题和答案 .pdf
《2022年大学数据结构考试题和答案 .pdf》由会员分享,可在线阅读,更多相关《2022年大学数据结构考试题和答案 .pdf(19页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第 1 章 绪论1、填空题1. 常见的数据结构有_线性 _结构, _树形 _结构, _图形 _结构等三种。2. 常见的存储结构有_顺序存储 _结构, _链式存储 _结构等两种。3. 数据的基本单位是_数据元素 _,它在计算机中是作为一个整体来处理的。4. 数据结构中的结构是指数据间的逻辑关系,常见的结构可分为两大类,_线性结构_和_非线性结构 _。2、应用题1、给出以下算法的时间复杂度. void fun(int n) int i=1,k=100; while(in) k=k+1; i=i+2; 时间复杂度为_O(n)_。2、给出以下算法的时间复杂度. void fun2(int n) int
2、 i=1,k=100; while(inext=p-next_;_p-next=s _;4. 在单向链表中,若要删除某个结点p,一般要找到 _p 的前趋 _结点,才能实现该操作。2、选择题1.将两个各有n 个元素的有序表归并成一个有序表,其最少的比较次数是A。(A)n (B)2n 1 (C)2n (D)n-1 2.在单链表中,如果在结点p 之后插入一个新结点s,其操作为 A 。(A)s-next=p-next; p-next=s; (B)p-next=s; s-next=p-next; (C)s-next=p; p-next=s-next; (D)p-next=s; s-next=p; 3.
3、若长度为 n 的线性表采用顺序存储结构,在其第i 个位置删除一个元素的算法的平均时间复杂度为( C ) 。(1i n)AO(0) BO(1) C.O(n) DO(n2) 4. 若长度为n 的线性表采用顺序存储结构,在其第i 个位置插入一个新元素需要移动的元素个数为( B ) 。(1i n+1)An-i Bn-i+1 C. i Dn-i-1 3、判断题1. 线性表中每一个元素都有一个前驱和一个后继。( )4、程序设计题1、单链表的结点结构定义如下:struct LinkNode 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师
4、精心整理 - - - - - - - 第 2 页,共 19 页 - - - - - - - - - LinkNode *next; int data; ; 请根据述函数的功能写程序。void Insert(LinkNode *h,LinkNode *s) /h指向链表的头结点(即使链表中没有元素,头结点也存在。)/ 链表中元素已经递增有序/ 函数功能为将结点s 插入到链表h 中。插入后链表仍然保持递增的顺序LinkNode *p,*q;/q指向 p 的前驱q=h; p=h-next; while(p) if(p-datas-data) /寻找到插入点位置,插入s q-next=s; s-nex
5、t=p; return; else q=p; (1分) p=p-next; (1分) / 当表中没有比s 大的结点时,插入到表尾s-next=q-next; (2分) q-next=s; (2分) 2、设顺序表L 是一个递增有序表,试写一算法,将x 插入 L 中,并使L 仍是一个有序表。顺序表的结构定义如下:#define ListSize 100 / 假定表空间大小为100 struct SqList int elemListSize; / 数组 elem 用于存放表中的数据int length; / 当前的表长度; / 以上为顺序表的结构/ 函数头定义如下void InsertIncrea
6、seList( SqList &L ,int x ) int i; if ( L.length=ListSize) cout0 & L.elem i-1 x ; i-) L.elem i =L.elem i-1 ; / 比较并移动元素名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 19 页 - - - - - - - - - L.elem i =x; /插入 x L.length+; /表长增 1 / 3、单链表中结点的结构如下所示:typedef struct node
7、 int data; struct node *next; node; 请设计满足下述功能的函数。要求:建立带头结点的单链表H ,要求函数从屏幕上读入m个整数,每读入一个,便生成相应的结点,并且把它插入到链表H 的尾部。函数形式为void CreateLinkList(node *H) 。参考程序:void CreateList(node *H) /H指向头指针int m,temp; coutm;/ int i=1; node *tail; H-next=NULL; tail=H; while(i=m) coutplease input your number:temp; node *t=ne
8、w node ; t-data=temp; t-next=tail-next; tail-next=t; tail=t; i+; 第 3 章 栈和队列1、填空题1. 栈和队列在本质上都是_线性表 _。2. 栈的操作特点是_后进先出 _。队列的操作特点是_先进先出 _。2、选择题1. 消除递归不一定需要使用栈,此说法_A_。A. 正确 B. 错误名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 19 页 - - - - - - - - - 2.对于栈,输入序列为(1,2,3,
9、4) ,不可能得到的输出序列有_D_。(A) (1,2, 3,4) (B) (4,3, 2,1)(C) (1,3, 4,2) (D) (3,1, 2,4)3. 用单循环链表表示队列,正确的说法是B。(A) 可设一个头指针使入队、出队都方便;(B) 可设一个尾指针使入队、出队都方便;(C) 必须设头尾指针才能使入队、出队都方便;(D) 无论如何 , 只可能使入队方便。3、判断题1. 栈的特点是先进先出。 ( )2. 可以在队列的任意位置插入元素。( )3. 递归程序化非递归程序必须用到栈。()4. 如果进栈的序列为(1,2, 3,4) ,则( 4,2,3,1)不可能是出栈序列。 ()5. 在用顺
10、序表表示的循环队列中,可用标志位来区分队空或队满的条件。()第 4 章 串1、选择题1. 设有两个串p 和 q,求 q 在 p 中首次出现的位置的运算称作(B)A连接 B模式匹配 C求子串 D求串长2、判断题1. 空串和空格串是同一个概念,二者没有区别。( )第 5 章 数组和广义表1、填空题1. 二维数组在内存中存储可以有两种存储方式,一种是 _行_优先存储,一种是列优先存储。2. 设广义表 L( () , () , ( () )) 。则 head(L) 是();tail(L)是( () , ( () )) ;L 的长度是3;L 的深度是 3 。3. 设广义表 L( (a) , (b) ,
11、( (c) )) 则 head(L) 是_(a)_;tail(L)是_(( b) , ( (c) ))_ _。2、选择题1. 在 C语言中,如果有数组定义 int A89;假定每个整型数据占2 字节,则数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 19 页 - - - - - - - - - 组元素 A44的地址是(A) 。A. A+80 B. A+76 C.A+82 D.以上都不对2. 广义表 A=(a,b,(c,d),(e,(f,g)), 则下面式子的值为( D
12、) ; Head(Tail(Head(Tail(Tail(A) A ( g) B.(d) C.c D.d 3、判断题1. 在 C语言中,多维数组的存储采取的是行优先的方式。( )2. 广义表在本质上也是线性表。()3. 可以用三元组存储法来压缩存储稀疏矩阵。( )4. 已 知 广 义 表A=(a,b,c),(d,e,f),从A中 取 出 原 子e的 运 算 是head(tail(head(tail(A)。 ( ) 第 6 章 树和二叉树1、填空题1. 一棵 62 个叶结点的完全二叉树, 最多有 _62*2=124_个结点。2. 若 规 定 仅 有 根 的 二 叉 树 的 高 度 为1, 那 么
13、 高 为h 的 完 全 二 叉 树 最 多 有 -_2h-1 _个结点,最少有_2(h-1) _个结点。3. 设只包含有根结点的二叉树的高度为0,则高度为k 的二叉树的最大结点数为-_2(k+1)-1_,最小结点数为_k+1_。4. 设仅包含根结点的二叉树的高度为1,则高度为k 的二叉树的最大结点数为-_2k-1 _,最小结点数为_k_。2、选择题1. 具有 N个结点的完全二叉树的深度是_B_。(A) ? log2N ?(B)? log2N ?+1 (C)? log2(N) ?(D)? log2N ?-12. 设二叉树的树根为第一层,则第i 层上至多有 _C _结点。(A)1 (B)2 (C)
14、2i-1 (D)2i-1 3、判断题1. 二叉树的左右子树次序是严格的,不能够任意改变。( )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 19 页 - - - - - - - - - 2. 若 根 为 第 一 层 , 则 深 度 为k的 满 二 叉 树 的 结 点 为2k-1 。( )3. 二叉树的三叉链表存储结构可以方便的访问到双亲结点。( )4、应用题1. 在一段文字中,共出现a、b、c、 d、e、f六种字符,每种字符出现的频率分别为7,9,12,22,23,27
15、。请回答下列问题:(1)什么是哈夫曼树?(3 分)(2)根据题目所给频率值,画出相应的哈夫曼树。(11 分)(3)给出各个字符对应的哈夫曼编码。(6 分)(4)该段文字经过哈夫曼编码后,长度是多少。( 4分)参考答案如下:(1)答案为: 带权路径长度最小的二叉树称为哈夫曼树。(3 分)(2)根据题目所给频率值,画出相应的哈夫曼树。(11 分,每个结点1 分)(3)给出各个字符对应的哈夫曼编码。(6 分)a:1110 b:1111 c:110 d:00 e:01 f:10 (4)该段文字经过哈夫曼编码后,长度是多少。( 4分)(7+9)*4+12*3+(22+23+27)*2=244 或者 10
16、0+45+55+28+16=244 2. 设一棵二叉树的先序遍历序列为abcde,中序遍历序列为badce,请画出对应的二叉树,并写出对应后序遍历序列。(15 分)参考答案如下:(1) 画出二叉树( 10 分)错一个结点扣2 分。f c 28 7 9 12 22 23 55 16 27 45 100 a b e d 1 0 0 0 0 0 1 1 1 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 19 页 - - - - - - - - - (2)后序遍历序列为:b
17、deca (5 分)3.通信报文中出现的字符A、B、C、D、E,在报文中出现的频率分别为0.23 、0.2 、0.32 、0.12 、0.13 ,分别给出相应字符的哈夫曼编码(要求画出哈夫曼树,并且把权值小的结点放在左边)。 (共 14 分)参考答案如下:为处理方便,关键字都乘以100,为 23 ,20, 32,12,13 构造哈夫曼树为:(9 分 , 每个结点 1 分)所以编码为: A:01 B :00 C:11 D :100 E :101 (5 分,每个编码1 分)4.某二叉树结点的中序序列为H,B ,C,D,E,F,G,后序序列为B,D,C,H,F,G,E,请据此画出该二叉树,再给该树加
18、上中序线索。(共 15 分)对应的二叉树为: (7 分, 每个结点1分)对应中序线索树为:(8 分,每条线索1 分)5A B D E C 0 1 0 0 0 1 1 1 100 43 57 20 23 25 32 12 13 a b c d e C F B D G H E C F B D G H E 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 19 页 - - - - - - - - - 5. 请证明对于任何一棵二叉树,如果其终端结点数为n0, 度为 2 的结点数为n
19、2, 则 n0=n2+1。(10 分)证明:令树中结点总数为N,度为 1 的结点个数为n1。则树中结点数满足下列公式:n0+n1+n2=N 从度的角度来考虑,满足下列公式:2n2+n1+1=N 从而得证: n0=n2+1 5.请按照孩子 - 兄弟表示法,将图1 所示树转化为二叉树。 (共 14 分)解:(每个结点2 分)6.设二叉树如图2 所示。分别写出它的先序遍历、中序遍历、后序遍历序列。 (共 15 分)8. (1)写出如图所示二叉树的中序遍历结果。(8 分)(2)画出二叉树的中序后继线索。(10 分)(1)中序遍历结果:ADBCHFEG 共 8 分,每个字符1 分(2)二叉树的中序后继线
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年大学数据结构考试题和答案 2022 大学 数据结构 考试题 答案
限制150内