安徽大学数据结构试卷a教学教材 下载本文

安徽大学数据结构试

卷2010A

-- -- - -- - -- - -- - -- - -- -- - -- - --号---学--- - -- - -- - 线- -- -- -- -- -- --名 -线---姓 -- -- --- 订-- -- -- -- 装-- -- -- 超-- 订- 勿-- --业题----专 -- -- -- 答-- -- -- -- -- -- -- --级----年---- -- -- -- 装- - -- - -- -- - -- -系---/--院------------ 精品文档

安徽大学20 09 —20 10学年第 2 学期

《 数据结构 》考试试卷(A卷)

(闭卷 时间120分钟)

题 号 一 二 三 四 五 六 七 总分 得 分 阅卷人

一、填空题(每空1分,共15分) 得分

1、在线性结构中,第一个结点 前驱结点,其余每个结点有且只有 个前驱结点;最后一个结点 后续结点,其余每个结点有且只有 个后续结点。 2、下面程序段的时间复杂度是 。

for (i=0;i

3、在具有n个单元的循环队列中,队满时共有 个元素。

4、假定一棵二叉树的结点数为18,则它的最小深度为 ,最大深度为 。 5、在一个单链表中p所指结点之后插入一个s所指结点时,应执行下面的操作:

s—>next=_ ___; p—>next=___;

6、从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时,其查找长度分别为 和 。

7、.一棵二叉树有67个结点,这些结点的度要么是0,要么是2。这棵二叉树中度为2的结点有___________________个。

8、在堆排序和快速排序中,若原始记录接近正序或反序,则选用____。

9、若采用邻接表的存储结构,则图的广度优先搜索类似于二叉树的________遍历。

二、单向选择题(每小题1.5分,共15分) 得分 1、n个顶点的强连通图中至少含有( )。

A、n—l条有向边 B、n条有向边 C、n(n—1)/2条有向边 D、n(n一1)条有向边

2、在一个不带头结点的单链表HL中,若要向表头插入一个由指针p指向的结点,执行( )。

收集于网络,如有侵权请联系管理员删除

精品文档

A、 HL=p; p一>next=HL; C、 p一>next=HL; p=HL;

B、 p一>next=HL;HL=p;

D、 p一>next=HL一>next; HL一>next

=p;

3、采用线性链表表示一个向量时,要求占用的存储空间地址( )。 A: 必须是连续的 B 部分地址必须是连续的 C: 一定是不连续的 D: 可连续可不连续

4、如果想在4092个数据中只需要选择其中最小的5个,采用( )方法最好。 A: 起泡排序 B: 堆排序 C: 锦标赛排序 D: 快速排序

5、在循环队列中用数组A[0..m-1] 存放队列元素,其队头和队尾指针分别为front和rear,则当前队列中的元素个数是( )。

A: ( front - rear + 1) % m B: ( rear - front + 1) % m C: ( front - rear + m) % m D: ( rear - front + m) % m

6、数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。 A: 1175 B: 1180 C: 1205 D: 1210

7、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( ) A: head(tail(LS)) B: tail(head(LS)) C: head(tail(head(tail(LS))) D: head(tail(tail(head(LS))))

8、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是( )。 A: bdgcefha B: gdbecfha C: bdgaechf D: gdbehfca 9、在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。 A: 1/2 B: 1 C: 2 D: 4

10、设串s1=’ABCDEFG’,s2=’PQRST’,函数con (x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度,则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是( )。 A: BCDEF B: BCDEFG C:BCPQRST D:BCDEFEF

三、应用题(每小题8分,共32分) 得分 1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算: 2.(1)第k层结点数(1≤k≤h)。 3.(2)整棵树结点数。

4.(3)编号为i的结点的双亲结点的编号。

5.(4)编号为i的结点的第j个孩子结点(若有)的编号。

收集于网络,如有侵权请联系管理员删除

精品文档

- ---- ---- ----

-----2已知图G的邻接表如图1所示,请写出:

-----(1)其从顶点v1出发的深度有限搜索序列; ------(2)其从顶点v1出发的广度优先搜索序列。

----

--- v1 ---线 V2 V5 V4 ^ --- ---- v2 v3 V5 ^ ----- -- -线--

v3 V6 ^ - -- -

--订---

v4 ^ - -- -

装--- --

v5 V4 V6 V3 ^ -超- --- 勿订- - -- -- v6 ^ 题-- -- - --答-- -----

---- 图1 图G的邻接表 ------ ----- ----- ----- 装-- ---- ---- ---- ---- ---- ---- ---

-3、 以关键码序列(503,087,512,061,908,170,897,275,653,426),为例,手工执行快速排序排序算法,写出每一趟排序结束时的关键码状态:

收集于网络,如有侵权请联系管理员删除