《2022年数据结构专升本习题集 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构专升本习题集 .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、网计 (专升本 )数据结构试题(模 A) 2004-5-1 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D) 写在下表中 ,答题写在其它地方无效；每小题1 分,共 11 分) 题号1 2 3 4 5 6 7 8 9 10 11 答案1.数据的不可分割的基本单位是_。 A.元素 B.结点 C.数据类型 D.数据项2.下列算法suanfa2的时间复杂度为_。int suanfa2(int n) int t=1 ；while(t0)个结点的完全二叉树的深度是_。 A.log2(n) B.log2(n)+1 C.?log2(n+1)? D.?log2(n)+1?7.
2、与中缀表达式a+b*c-d 等价的前缀表达式是_。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.abcd+*- 8.折半查找有序表(6,15,30,37,65,68,70,72,89,99), 若查找元素37,需依次与表中元素 _进行比较 ,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,37 9.对长度为10 的表作选择 (简单选择 )排序 ,共需比较 _次关键字。 A.45 B.90 C.55 D.110 10.对 n 个元素的表作快速排序,在最坏情况下,算法的时间复杂度为_。 A.O(log2 n) B.O(nlog2 n)
3、 C.O(n2) D.O(2n ) 共 5 页第 1 页11.对长度为10 的表作 2_路归并排序 ,共需移动 _次(个)记录。 A.20 B.45 C.40 D.30 二、填空 (每空 1 分,共 11 分) 1.一个数据结构在计算机中的表示(映象 )称为 _? 。2.线性表中 _ 称为表的长度。3.栈中元素的进出原则为 _ 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 4.设数组A1.10,1.8 的基地址为2000,每
4、个元素占2 个存储单元 ,若以行序为主序顺序存储,则元素A4,5 的存储地址为_；若以列序为主序顺序存储,则元素A4,5 的存储地址为_。5.一棵深度为6 的满二叉树有_个非终端结点。6.若一棵二叉树中有8 个度为 2 的结点 ,则它有 _个叶子。7.顺序查找n 个元素的顺序表,当使用监视哨时,若查找成功 ,比较关键字的次数至少为_次, 最多为 _次；若查找失败,比较关键字的次数为_次。8.对长度为400 的表采用分块(区)查找 ,最理想的块长为_。三、回答下列问题 (每小题 5 分,共 10 分) 1.线性表的存储结构,在什么情况下采用顺序结构? 为什么 ? 2.二叉树有哪几种基本形态? 画
5、图说明之。四、试画出下列存储结构图(每小题 4 分,共 20 分) 1.数组 A1.2,0.2 的以列序为主序的顺序存储结构。共 5 页第 2 页2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。3.二叉树的顺序存储结构: 4.图的邻接矩阵: 5.有向图的逆邻接表: 五、求解下列问题 (每小题 6 分,共 24 分) 1.给定 30 个字符组成的电文: D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D 试为字符 A、B、C、D、E、F 设计哈夫曼 (Huffman) 编码。 (1
6、)画出相应的哈夫曼树； (2)分别列出 A、B、C、D、E、 F 的哈夫曼码；(3)计算该树的带权路径长度WPL。共 5 页第 3 页2.试按表 ( 10,8,9,12,20,5,6,15,19,25 ) 中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中 , 使之仍是一棵二叉排序树。 (1)试画出插入完成之后的二叉排序树； (2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小? (3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。 (4)对该树进行中序遍历,试写出中序遍历序列。3.试将森林 F= T1,T2,T3,T4 转换为一棵二叉树。 T1 T2 T3
7、T4 4.找出下面网络的最小生成树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 六、填空题 (在算法中有下划线_的位置填空 ,使之成为完整、正确的算法) 算法说明 :已知 r1.n 是 n 个记录的递增有序表,用折半查找法查找关键字为k 的记录 ,若查找失败 ,则输出 ”Failure ”,返回零；否则输出”Success”,并返回该记录的序号值。(共 8 分) 算法 (C 函数 ): 共 5 页第 4 页int bin_s
8、earch(struct arecord r,int n,k:keytype) /* r1.n 为 n 个记录的递增有序表,k 为关键字 */ int low, mid, hig ； low=1 ； hig=n ； /* 各变量初始化 */ while( _ ) mid=_ ； if(krmid.key) _ ； else if(k=rmid.key) _ ； _ ； else _ ； _ ； _ ； 七、算法设计 (算法中必须有注释,每小题 8 分,共 16 分) 1.设 n 个元素的线性表顺序存储在一维数组st1.maxlen 的前 n 个位置上 ,试将新元素e插入表中第 i-1 个和第
9、i 个元素之间 ,写出算法。2.设 Head 为带表头结点的单链表的头指针,试写出算法 :若为非空表 ,则输出首结点和尾结点的值 (data值)；否则输出 : ”Empty list ！” 。共 5 页第 5 页网计 (专升本 )数据结构试题(模 B)2004-5-1 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D) 写在下表中 ,答题写在其它地方无效；每小题1 分,共 11 分) 题号1 2 3 4 5 6 7 8 9 10 11 答案1.数据的基本单位是_。 A.结点 B.数据元素 C.数据类型 D.数据项2.下列算法suanfa1中语句 x=x*2 ；
10、的执行次数是_。 void suanfa1(int n) int i,j,x=1 ； for(i=1 ；i=n ；i+) for(j=i ；j0)个结点的完全二叉树的深度是_。 A.log2(n)+1 B.log2(n)-1 C.?log2(n)-1? D.?log2(n)+1?9.与中缀表达式a-b/c+d 等价的前缀表达式是_。A.-a+/bcd B./-+bcd C.+-/bcd D.abcd-/+ 10.对有 3600 个记录的索引顺序表(分块表 )进行查找 ,最理想的块长为_。A.1800 B.60 C.1200 D.log2 3600共 5 页第 1 页11.对 n 个元素的表作堆
11、排序,在最坏情况下 ,算法的时间复杂度为_。 A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n ) 二、填空题 (每空 1 分,共 11 分) 1.一个算法具有5 个特性 :_、_、_、有零个或多个输入、有一个或多个输出。2.设长度为n 的线性表顺序存贮,若在它的第i-1 和第i 个元素之间插入一个元素, 共需移动 _ 个元素 (1i n) 。3.一个字符串中 _ 称为该串的子串。4.树中结点A 的 _ 称为结点A 的度。5.一棵深度为4 的二叉树最多有 _ 个结点。6.具有 10 个顶点的无向图,边的总数最多为 _ 。7.顺序查找n 个元素的顺序表,当不使用监视
12、哨时,若查找成功,比较关键字的次数最多为 _ 次；若查找失败,比较关键字的次数为 _ 次。8.折 半 查 找 有 序 表 ( 2,4,6,12,20,28,38,50,70,100 ), 若 查 找 表 中 元 素12, 它 依 次 与 表 中 元素 _ 比较大小。三、回答下列问题 (每小题 5 分,共 10 分) 1.线性表的存储结构,在什么情况下采用链接表(如:单链表 )结构 ?为什么 ? 2.空格串与空串有区别? 举例说明之。共 5 页第 2 页四、试画出下列存储结构图(每小题 5 分,共 20 分) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -
13、- - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 1.试画出下列稀疏矩阵以列序为主序的三元组表。稀疏矩阵2.试画出下列二叉树的中序线索二叉树存储结构图。二叉树3.试用孩子兄弟(左孩子右兄弟)表示法画出下列树的存储结构图。树4.试画出下列有向网的逆邻接表。有向网共 5 页第 3 页五、求解下列问题 (每小题 6 分,共 24 分) 1.已知二叉树的前序遍历序列和中序遍历序列分别是：B,A,C,D,F,E,G 和 D,C,A,F,G,E,B, 试画出该二叉树。2.试按表 (25,15,19,24,20,5,16,45,
14、40,38) 中元素的排列次序,将所有元素插入一棵初始为空的二叉排序树中 ,使之仍是一棵二叉排序树。(1)试画出插入完成之后的二叉排序树；(2)若查找元素 17,它将依次与二叉排序树中哪些元素比较大小?(3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL；(4)对该树进行中序遍历,试写出中序遍历序列。3.试用权集合4,6,5,12,2,1,13, 构造赫夫曼(Huffman) 树,(1)列出构造过程, (2)分别计算该赫夫曼树的路径长度和带权路径长度。4.找出下面网络的最小生成树: 共 5 页第 4 页六、执行下面的C 程序 ,指出输出结果。(8 分) #include #inc
15、lude struct node char data； struct node *next ； ； void link_list(struct node *p) while(p!=NULL) printf(%c,p-data)； p=p-next ； printf(n) ； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - main( ) char ch ； struct node *q,*p,*f,*head=NULL； for
16、 (ch=A ；chdata=ch； p-next=head； head=p； link_list(p) ； p=head； head=NULL ； while(p!=NULL) q=p ； p=p-next； q-next=head； head=q； f=head； while(f-next!=NULL) link_list(head) ； f=f-next-next ； 七、算法设计 (算法中必须有注释,每小题 8 分,共 16 分) 1.设 n 个元素的线性表顺序存储在一维数组 st1.maxlen 的前 n 个位置上 ,试写出算法 :删除表中第 i(1 i n)个元素。2.设 Head
17、 为带表头结点的单链表的头指针,试写出算法 :若为非空表 ,则输出 :最大结点和最小结点的值 (data值 )；否则 ,输出 : “Empty list”。共 5 页第 5 页网计 (专升本 )数据结构试题(模 C) 2004-5-1 一、选择题 (从下列各题的4 个备选答案中选出1 至 2 个正确答案 ,将其代号 (A,B,C,D) 写在下表中 ,答题写在其它地方无效；每小题1 分,共 15 分 ) 题号1 2 3 4 5 6 7 8 9 10 11 12 12 14 15 答案1.由_组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类
18、型的数据元素2._是线性表。A.(孔子 ,诸葛亮 ,曹雪芹 ) B.A,B,C,D C.10,11,12,13,14 D.(1,2,3,.) 3._ 是表示线性数据结构的。 A.循环链表 B.邻接多重表 C.孩子链表 D.单链表4.将线性表的数据元素以_结构存放 , 查找一个数据元素所需的时间不依赖于表的长度。 A.循环双链表 B.哈希 (Hash)表 C.一维数组 D.单链表5.设数组 A1.8,1.10 的基地址为4000, 每个元素占2 个存储单元 ,若以列序为主序顺序存储,则元素 A4,7 的存储地址是_。(假定无第0行第 0 列元素 ) A.4072 B.4104 C.4102 D.
19、4074 6.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_。 A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b 7._ 又是一棵满二叉树。 A.二叉排序树 B.深度为 5 有 31 个结点的二叉树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - C.有 15 个结点的完全二叉树 D.哈夫曼 (Huffman) 树8.深度为 k 的满二叉树有_个分枝结点。 A.2k-1 B.2
20、k-1-1 C.2k+1 D.2k-1+1 9.具有 n(n0)个结点的完全二叉树的深度为_。 A.log2(n) B.?log2(n)? +1 C.log2(n+1) D.?log2(n+1)?10.折半查找20 个记录的有序表,若查找失败 ,比较关键字的次数_。 A.最多为 6 B.最多为 5 C.最少为 3 D.最少为 4 11.折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次与表中元素 _进行比较。 A.25,40,60 B.25,40 C.20,36,40,60 D.20,36,40 12.查找哈希 (Hash)表 ,解决冲突的的方法有_。 A.除留
21、余数法 B.线性探测再散列法 C.直接地址法 D.链地址法共 5 页第 1 页13.对有 10 个记录的表作简单选择排序,需要比较 _次关键字。 A.100 B.45 C.50 D.90 14.对有 n 个记录的表作快速排序,在最坏情况下,算法的时间复杂度是_。 A.O(n) B.O(n2) C.O(nlog2n) D.O(n3) 15.一个排序算法时间复杂度的大小_有关。 A.与所需比较关键字的次数 B.与该算法的稳定性 C.不与所需移动记录的数目 D.与所需辅助存储空间的大小二、画图题 (每小题 4 分,共 20 分) 1.依次输入元素X,Y,Z, 插入到一个初始状态为空的链式栈中,试画出
22、空的链式栈和每插入一个元素之后的链式栈示意图。2.试用双亲表示法画出下列树T 的存储结构图。3.试画出有3 行 4 列元素的二维数组B 的以列序为主序的顺序存储结构图。4.试画出下列图的邻接表。图共 5 页第 2 页5.已知一棵二叉树的前序遍历序列和中序遍历序列分别是： I,A,B,E,F,G,C,H,D 和 A,E,F,B,I,G,H,C,D 试画出该二叉树。三、求解问题 (每小题 7 分,共 28 分) 1.用算符优先法求下列算术表达式的值,试简要说明求值过程,画出操作数栈和运算符栈的主要变化过程。 12+20/(10-2*3) 2.给定电文 (文本 ): F F A A A B B B
23、A A A B B C C C D E G G G试为字符 A、B、C、D、E、F、G 设计哈夫曼 (Huffman) 编码 :(1)画出相应的哈夫曼树,列出各字符的哈夫曼码；(2)计算该哈夫曼树的带权路径长度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 共 5 页第 3 页3.假定后序遍历二叉树的结果是A,C,B,(1) 试画出所有可得到这一结果的不同形态的二叉树；(2)分别写出这些二叉树的中序遍历序列。4.假定对 20
24、个记录的表作折半查找,(1)试画出描述折半查找过程的判定树；(2)若每个记录的查找概率相等 ,试计算查找成功时的平均查找长度。四、分析算法回答问题(每小题 10,共 20 分) 1.算法 (C 函数 ) int suanfan(int n) int i,j,sum=0 ；for (i=0 ；i=n；i+) for (j=i ；jn；j+) sum+ ； printf(i=%d,j=%d,sum=%dn,i,j,sum)； return sum； 试回答问题 : (1)jdata)； traversal(root-lchild) ； printf(%c,root-data) ； traversa
25、l(root-rchild) ； 五、设计算法 :输入一个m*n 的整数矩阵 ,如果各个元素互不相同,则输出信息 没有重码 !；否则输出信息 有重码 :和重码值 (相同的元素 )。1.用 C 语言写出所用数据结构的类型定义和算法；2.分析算法的时间复杂度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - (共 17 分) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -