南理工09数据结构A

《南理工09数据结构A》由会员分享，可在线阅读，更多相关《南理工09数据结构A（3页珍藏版）》请在装配图网上搜索。

1、南京理工大学课程考试试卷 （学生考试用）课程名称： 数据结构 学分： 3.5 大纲编号 06022402-0试卷编号： A 考试方式： 闭卷 满分分值： 80 考试时间： 120 分钟组卷日期： 2009年12月18日 组卷教师（签字） 赵学龙 审定人（签字） 学生班级： 理学院 学生学号： 学生姓名： 一、 选择题（1*20=20分）1. 以下数据结构中，（ ）是非线性数据结构。A树 B字符串 C队 D栈2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表3. 若长度为n的线性

2、表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=i=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 4. 栈和队都是（ ）A顺序存储的线性结构 B. 链式存储的非线性结构C. 限制存取点的线性结构 D. 限制存取点的非线性结构5. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。AXYZ B. YZX C. ZXY D. ZYX6. 数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是( )。A. 1175 B. 1180 C. 12

3、05 D. 12107. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为 ( ) 。A不确定 B2n C2n+1 D2n-19. 下述编码中哪一个不是前缀码（ ）。A（00,01,10,11） B（0,1,00,11） C（0,10,110,111） D（1,01,000,001）10. 设无向图的顶点个数为n，则该图最多有（ ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 Dn211. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。A.

4、 O(n) B. O(n+e) C. O(n2) D. O(n3)12. 关键路径是事件结点网络中（ ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路13. 下列哪一种图的邻接矩阵是对称矩阵？（ ）。A有向图 B无向图 CAOV网 DAOE网14. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。A. LL B. LR C. RL D. RR15. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，7

5、2，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。A 8 B. 9 C. 10 D. 1116. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为(1) 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。 A. 选择 B. 冒泡 C. 快速 D. 插入17. 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依此写入缓冲区，而打印机则依此从该缓冲中取出数据打印，该缓冲区

6、应该是一个 ( ) 结构。A线性表 B.数组 C.栈 D.队列18. 假定有一批数据中有k个关键字是相同的，若用线性探测再散列的方法把这k个数据存入哈希（散列）表中，至少需要进行 ( ) 次探测。Ak-1 Bk Ck+1 Dk(k+1)/219. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（i1) sum=1；for (i=0;sumn;i+) sum+=1; 2. 在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是（2） 。3. 循环队列用数组A0.m-1存放其元素值，已知其头

7、尾指针分别是front和rear ，则当前队列的元素个数是 (3) 。4. 所谓稀疏矩阵指的是 (4) 。 5. 深度为H 的完全二叉树中H和结点总数N之间的关系是 (5 ) 。6. 在一棵二叉树中，度为1的结点有40个，总的结点数为99，则二叉树中叶子结点数共有 （6） 。7. 中缀式a+b*3+4*（c-d）对应的前缀式为 (7) 。 8. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是 （8） 。9. 对n个记录的表r1.n进行简单选择排序，所需进行的关键字间的比较次数为 （9） 。10. 构造连通网最小生成树的两个典型算法是 （10） 。三、 简答题（35分）1(每小题3分,共计

8、15分)已知某图的邻接表为（1）写出此邻接表对应的邻接矩阵； （2）写出由v1开始的深度优先遍历的序列； （3）写出由v1开始的深度优先的生成树； （4）写出由v1开始的广度优先遍历的序列； （5）写出由v1开始的广度优先的生成树；2(每小题3分,共计9分)在快速排序和归并排序中： (1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？3. (3分)试述头结点,首元结点,头指针这三个概念的区别. 4(4分)将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）GHIJABCDEF5. （4分）有4个结点，权值分别为7，5，2，4，构造一棵哈夫曼树，并求其带权路径长度。四、 算法设计（用类-C/类-C+描述）（15分）1(7分) 写出一趟快速排序算法。2(8分)已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。 第 3 页 共 3 页