数据结构09级信本期中试卷 2011.5.5

?????????? _?_?__?_?__?_?号?学线 ? ? ? ?__?_?__?_?__?_?_名??姓? ? ? 封 _?_?__?_?__?_?级?班? ? ? ? ?__?_密__?_?__?业?专???????????河北北方学院2010-2011学年第二学期期中考试试卷

《数据结构》

（供 医学信息本科 专业使用）

注意事项：

1．请按要求在试卷的密封区填写专业、班级、姓名和学号。 2．请仔细阅读各种题目的答题要求，在规定的位置填写答案。

3．不要在试卷上乱写乱画，不要在密封区填写无关的内容。 题号 一 二 三 四 五 总分 得分

总分合计人： 复核人：

得分 评卷人 一、填空

（共20分，每空1分。）

1. 宏观地讲，数据结构是一门研究非数值性程序设计中计算机操作的________________________的学科。 2. 下面程序段的时间复杂度为________。 for (int i=0;i

3. 我们以程序语句的_________ _即 _______作为时间量度，

来做为程序效率分析的标准。

4. 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如

本试卷共 8 页 第 1 页

果6个元素的出栈顺序为 s3, s2, s5, s6, s4, s1，则顺序栈的层数至少为_______。

5. 一个链队列中，若front指针等于NULL通常为_ _ ___，rear指针等于 NULL通常为____ _。

6. n维数组是一个同构的数据结构，即它的每一个数据元素均属于_____ _________ _或 。

7. 若将结点New插入单链表中，*p指向欲插入结点，将New插入其后端, 语句如下：

p->Next = New；New->Next = p->Next； 则会产生的问题是____________。

8. 对于数组仿真的堆栈，若事先分配的存储空间为Maxsize=Maxtop+1，表 示指针的向量为top，则push操作中产生上溢的指针情况________________， 如此可能产生的情况是___________。若以temp做为暂存出栈元素的变量， 请描述pop操作的主要步骤：________________________________________。 9. 使用环状队列解决空间利用问题，若以数组描述队列，事先分配的存储空 间长度为Maxsize，则环状队列的有效利用空间为___________； 队首（或队 尾）指针的前移方式为：______________ ______________。

10. 函数调用过程中，调用函数和被调函数之间的链接和信息交换需要通 过_____来进行。当有多个函数构成嵌套调用时，遵循_____ ___ ____原则。 11. 普通树形结构与二叉树的二叉链表的表示法中，唯一不同就是其右指针指向的是___________ ____。

12. 当以二叉链表作为树或森林的存储结构时，可以使用二叉树的 两种方式遍历一棵树或森林。

13. 中序线索满二叉树中非终端结点的直接前驱是___________ ___ _____。 得分 本试卷共 8 页 第 2 页

评卷人 二、选择题

（共10分，每题1分。）

1. 循环单链表不具有的特点是【 】

A．具备随机访问特性 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．循环单链表可由头点或尾结点确定 2. 堆栈和队列都是【 】

A．顺序存储的线性结构 B．链式存储的顺序结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 3. 设三个函数f、g、h ，函数式分别为：

f(n)＝100n3＋n2＋1000 g(n)＝25n3＋5000n2 h(n)＝n1.5＋5000nlgn。下列关系中不成立的是【 】

A. f(n)＝O(g(n)) B． g(n)＝O(f(n)) C．h(n)＝O(n1.5) D． h(n)＝O(nlgn) 4. 通常不属于队列应用范围的是 【 】

A．优先队列 B．操作系统中的工作调度 C．处理子函数的调用 D．用于打印缓冲“spooling” 5. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加【 】

A． 2 B． 1 C． 0 D． –1

6. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行【 】

A． s→link = p→link; q→link = s; B． p→link = s; s→link = q;

C． p→link = s→link; s→link = p; D． s→link = p ；q→link = s; 7. 对于树的特性，描述有误的是【 】

A．树是层次结构 B．树结点具备唯一的前趋与后继 C．递归是树固有的特性 D．N元树的分支度即为N 8. 有关如下声明，下列那个语句的指定是正确的？【 】

char *s1=”hello!”; char *s2=”excellent”; char *string; char s1[20];

本试卷共 8 页 第 3 页

A．s1=s2; B．s2=string; C．string=s1; D．s1[20]=*s2;

9. 对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为【 】 A. R-F B. n+R-F C. (R-F+1) mod n D. (n+R-F) mod n

10. 设有一个n?n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。

A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 得分 评卷人 三、判断题

（共10分，每题1分。）

1、在数组结构中，可根据给出的索引值，找到该数组的内容值，因此说数组中的数据具备随机存取性。........................................（ ） 2、线性表的逻辑顺序与物理顺序一致。...........................（ ） 3、基于链栈的元素序列，插入与删除运算只能在序列首进行。.......（ ） 4、对含有n个结点、树高为h的二叉树实施前、中、后序遍历，空间复杂度均为O(h)。.......................................................（ ） 5、C语言中，字符串在函数间是以传址调用的方式进行传递的，形参就是字符串的名称。....................................................（ ） 6、具有n个结点的完全二叉树的深度为不大于log2n的整数。.......（ ） 7、在程序运行过程中可以扩充的数组是动态分配的结构数组。这种数组在声明它时需要使用数组指针。........................................（ ） 8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。......................................................（ ） 9、通常递归的算法简单、易懂、容易编写，而且执行的效率也高。...（ ） 10、对于树进行后序遍历的结果等于对其相应的二叉树中序遍历的结果；树的

本试卷共 8 页 第 4 页

先序遍历结果等于对其相应二叉树先序遍历的结果。....（ ） 得分

评卷人 四、综合题

（共35分。每题占分在题后标注。）

1、有一稀疏矩阵如右下表所示。请描述其存储方式。（7分）

0 1 2 3 4 5 6 7 8 0 0 0 3 0 2 0 0 0 0 1 1 0 0 4 0 0 0 7 0

2 0 5 0 0 0 6 0 0 0

3 0 0 0 0 0 0 0 0 0 4 0 0 0 9 0 0 0 8 0 5 0 0 0 0 0 0 0 0 0

2、设有一个长整型的二维数组共有7行8列，在内存中的起始地址为 100。请求出以列为主序进行数据存储时，第5行第6列的元素的内存 地址。（5分）

3、现有一个班级40个同学的姓名、性别、年龄和住址, 请将学生资料 定义成一个结构数组。并列出对结构数组成员的访问形式（列出一二项 即可）。（5分）

本试卷共 8 页 第 5 页

本文来源：https://www.bwwdw.com/article/23zf.html