Question

！！！高分求数据题目的答案！！！

)《数据结构》试题(模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.数据项

7.与中缀表达式a+b*c-d等价的后缀表达式是____。
A.+a-*bcd B.*+-abcd
C.-+a*bcd D.abcd+*-
8.折半查找有序表(10,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

二、填空(每空1分,共11分)
1.一个数据结构在计算机中的表示(映象)称为 ________________。
2.线性表中 ____________________________ 称为表的长度。
3.栈中元素的进出原则为 _____________________ 。
5.一棵深度为6的满二叉树有______个非终端结点。
6.若一棵二叉树中有8个度为2的结点,则它有_____个叶子。
7.顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为____次, 最多为____次；若查找失败,比较关键字的次数为____次。
三、回答下列问题 (每小题5分,共10分)
1.线性表的存储结构,在什么情况下采用顺序结构? 为什么?
2.二叉树有哪几种基本形态? 画图说明之。
四、试画出下列存储结构图(每小题4分,共20分)
1.数组A[1..2,0..2] 的以列序为主序的顺序存储结构。

2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。

2.试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。
(1)试画出插入完成之后的二叉排序树；
(2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小?
(3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。
(4)对该树进行中序遍历,试写出中序遍历序列。

七、算法设计(算法中必须有注释,每小题8分,共16分)
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。
最重要是解答这题:
算法设计(算法中必须有注释,每小题8分,共16分)
1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。
2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。

Answer 1

一
1. 数据项
7. 题目错了吧。。应该是前缀-+a*bcd 后缀的话应该是abc*+d-
8. 65 15 30
二
1. 数据的物理(存储)结构
2. 数据元素的个数
3. 后进先出
5. 2^5-1=31

呃。。。下班了。。约会去咯

Answer 2

恢复合乎