数据结构试题及答案

时间:2014-03-13

大学计算机专业《数据结构》期末试题及参

一、单项选择题（每小题1分，共12分） 1．下面算法的时间复杂度为( )． int f(unsigned int n) { if(n==0||n==1)return 1; else return n * f(n-1); }

A, 0(1) B. O(n) C. O(n2) D. O(n!)

2.在一个长度为n的顺序表中顺序查找一个值为x的元素．在等概率的情况下，搜索成功时间元素的平均比较次数为( )．

A. n B. n/2 C. (n+l)/2 D. (n-1)/2

3．带头结点的单链表first为空的判定条件是( )．A. first== NULL;

B. first->link ==NULL C. flrst->link==first D. first!= NULL

4．已知L是一个不带表头的单链表的表头指针，在表首插入结点*p的操作是( ) A. p=L; p->link=L; B. p->link=L; p=L; C. p->link=L; L=P; D. L=p; p->link=L;; 5．设循环队列的结构是 struct Queue {

DataType data[MaxSize]; int front, rear; };

若有一个Queue类型的队列Q．试问判断队列满的条件应为( )．

A. Q. from==Q, rear;

B. Q. front==Q. rear==MaxSize; C. Q. front+Q, rear= =MaxSize; D. Q. front==(Q, rear+l) % MaxSize;

6．设有一个广义表A((x．(n，b))，(x，(9。b)，y))，运算Head(Head(Tail(A)))的执行结果为( )． A．x B．(a，b) C．(x，(a ，b)) D．y

7．在一棵完全二叉树中，著编号为i的结点存在左子女，则左子女结点的编号为( )． 假定树根结点的编号为0。 A．2i B．2i一1 C．2i+1 D．2i+2

8．对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1／8，搜索后面5个元素的概串相同，均为3／40，则搜索任一元素的平均搜索长度为( )． A．5．5 B．5 C 39／8 D．19／4

9．向一棵AVL树插入元素时，可能引起对最小不平衡于树的左单或右单旋转的调整词程，此时需要修改相关( )个指针域的值．

A．2 B3 C．4 D 5

10．对于有向图，其邻接矩阵表示比邻接表表示更易于( )．

A．求一个顶点的入度 B．求一个顶点的出边邻接点 C．进行图的深度优先遍历 D．进行图的广度优先遍历 l1．设有向固有n个顶点和，条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )． A. O(nlog2e) B. O(n+e) C. O(ne) D. O(n2) 12．在10阶B树申报结点所包含的关键码个数最少为( )． A．O B1 C．3 D4

试题答案及评分标准

一、单项选择题 (每小题1分，共12分)

1．B 2．C 3.B 4．C 5．D 6．A 7．C 8．C 9．B 10．A 11．B 12．B 二，填空题．在横线处填写合适内容{每空1分，共16分) 1.属性与服务相同的对象构成类，类中的每个对象称为该类的__________·

2．在类的继承结构中，位于上层的类叫做__________，其下层

的类则 叫做__________类．

3．若设串S＝“documentHash.doc\\O”，则诙字符串S的长度为__________·

4．线性表的链接存储只能通过__________顺序访问。

5．设链栈中结点的结构为(data，link)，栈顶指针为top，则向该链栈插入—个新结点*p时，应依次执行__________和__________操作。

6．广义表的深度定义为广义表中括号被嵌套的__________· 7．在一棵高度为h的完全二叉树中，最少含有__________个结点。假定树根结点的高度为O。

8．从有序表(12，20，30，43，56，78，92，95)中折半搜索56、78和98元素时，其搜索长度分别 为__________、__________和__________·

9。n个(n>0)顶点的连通无向图中各顶点的度之和最少为______·

10．设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为__________·

11．给定一组数据对象的关键码为{ 46，79，56，38，40，84 }，则利用堆排序方法建立的初始最大堆的堆首和堆尾的关键码分别为________和________·

12．在索引表中，着一个索引项对应数据对象表中的一个表项，

则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为________索引．

计算机专业 数据结构 试题答案及评分标准

二、填空题，在横线处填写合适内容(每空1分，共”分) 1．实例

2．基类 派生类(或子类) 3．16 4．链接指针

5．p->Link = top; top = p; 6．重数 7．2h

8． 3 2 5 9．2(n-1) 10。O(n2) 11．84 46 12。稀疏

三、判断题，在每小题后面的括号内打对号表示正确或打叉号表示错误(每小题1分，共12分)

1．算法和程序都应具有下面—些特征：有输入，有输出，确定性，有穷性，有效性。 ( )

2．用C字符数组存储长度为n的字符串，数组长度至少为n+1． ( )

3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针．( )

4．—个广义表的表尾总是一个表． ( )

5．在树的存储中，若使每个结点带有指向双亲结点的指针t将在算法中为寻找双亲结点带来方便． ( ) 6．假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意—个集合单链表的长度． ( )

7．邻按矩阵适用于稀疏图(边数远小于顶点数的平方)，邻接表适用于稠密图(边数接近于顶点数的平方)． ( ) 8．对一个无向连通图进行一次深度优先搜索可以追访图中的所有顶点． ( )

9．在任何情况F，快速排序需要进行关键码比较的次数都是O(nlog2n)． ( )

10．在索引顺序结构的搜索中．对索引表既可以采取顺序搜索，

也可以采用折半搜索．( )

11．对于一棵具有n个结点。高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)． ( ) 12．图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变． ( )

计算机专业 数据结构 试题答案及评分标准 三、判断题 (每空1分，共12分)

1．错 2．对 3．对 4．对 5．对 6．对 7．错 8．对 9．错 10．对 11．错 12．对 运算题(每小题6分，共30分)

1．设有一个lOxl0的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[5][8]存放于B中什么位置．

A[5][8]在B中的存放位置：

2．有7个带权结点，其权值分别为3，7．8，2，6，10，14，试以它们为叶子结点生成一棵霍夫曼树，求出该树的带权路径长度和高度，假定树根的高度为0． 带权路径长度： 高度：

3．已知有向图G(V，E)，其中V={a，b，c，d，c}，

E＝{，，，，，，}

请问该图的邻接表中，每个顶点单链表各有多少边结点． 顶点： a b c d e 边结点数：

4．已知一个AOV网络的顶点集V和边集E分别为： V={O，1，2，3，4，5，6，7}；

E={<0，2>，<1，3>，<1．4>，<2，4>，<2，5>，<3，6>，<3，7>，<4，7>，<5，7>，<6，7>)，

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的，则按教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列(提示：先画出对应的图形，然后再运算)． 拓扑序列：

5．已知有一个数据表为{30，18，20，15，38，12，44，53，46，18，26，86}，给出进行归并排序的过程中每一趟排序后的

数据表的变化．

(0) [30 18 20 15 38 12 44 53 46 18 26 86] (1) (2) (3) (4)

试题答案及评分标准

四、运算题(每小题6分，共30分) 1． 43

答案说明：根据题意，矩阵A中当元素下标i与j满足i≤j时，任意元素A[i][j]在一维数组B中的存放位置为(2。n一1—1)*1／2+J，因此，A[5][8]在数组B中的位置为： (2*10—5—1)*5／2+8=43 2．带权路径长度：131，高度：4

3．评分标准：每个数据对给1分，全对给6分． 顶点： a b c d e 边结点数： 1 1 2 1 2

4．评分标准；若与答案完全相同得6分，若仍为一种拓扑序列用得3分，其他用酌情处理．

拓扑序列：1，3，6，0，2，5，4，7。

5．分步给分

(0)[30 18 20 15 38 12 44 53 46 18 26 86] (1)[18 30] [15 20] [12 38] [44 53] [18 46] [26 86] (2)[15 18 20 30] [12 38 44 53] [18 26 46 86] (3)[12 15 18 20 30 38 44 53] [18 26 46 86] (4)[12 15 18 18 20 26 30 38 44 46 53 86] 算法分析题 (每小题6分，共18分)

1.设字符串类String具有下列操作：

int Length() const； // 计算字符串的长度 char getData(k)； // 提取字符串第k个字符的值若字符串Tar的值为“ababcabcacbab”，Pat的值为“abcac”，

(1)给出下面算法执行后返回的结果， (2)给出下面算法的功能。 include \"String, h\"

int unknown(String& Tar, String& Pat) coast {

for (int iwhile (jif(Tar.getOata(i+j) == Pat.getData(j)) j++; else break;

if (j==Pat.Length()) return i;

}

return –1； }

返回结果： 算法功能：

2。已知二叉树中的结点类型BinTreeNode定义为：

struct BinTreeNode { ElemType data; BinTreeNode * left, * right; }

其中data为结点值域，left和right分别为指向左、右子女结点的指针域．下面函数的功能是返回二叉树BT中值为X的结点所在的层号．根据题意按标号把合适的内容填写到算法后面相应标号的位置．

int NodeLevel(BinTreeNode * BT, ElemType X) { if (BT==NULL) return -1; // 空树的层号为-1 else if (BT->data==X) return 0; // 根结点的层号为0 // 向子树中查找X结点

else {

int cl = NodeLevel(BT->left, X); if (cl>=0) ________________ ; (1) int c2 = __________________ ; (2) if ( (3) ) return c2+1； else return -1; // 若树中不存在X结点则返回-l } } (1) (2) (3)

3．假定一个有向无权图采用邻接矩阵存储，请指出下面算法的功能。

Template

void Graph::unknown(int i) {

int d, j； d=0;

for (j=0; jif (Edge[i][j]) { d++; Edge[i][j]=0; } if (Edge[j][i]) { d++; Edge[j][i]=0; } }

CurrentEdges -= d; // CurremEdges为图中的边数 }

算法功能：

计算机专业 数据结构 试题答案及评分标准 五、算法分析题(每小题6分，共18分) 1. 返回结果，5

算法功能：字符串的模式匹配算法． 2． (1) return cl+l;

(2) NodeLevel(BT->right，X) (3) c2>=0

3. 从有向无权图中删除与顶点i相连的所有边，包括出边和入边。

算法设计题(每小题6分．共12分)

1．请写出在循环队列上进行插入操作的算法。要求若插入成功则返目true，否则返回else．

循环队列定义如下： struet CyclicQueue {

ElemType elem[M]; // M为已定义过的整型常量，表示队列数组空间长度

int rear, front; // rear指向队尾元素后一个位置， // front指向队头元索 int tag; };

注意：当front==rear且tag==0时，队列空，当front＝rear且tag＝1时，队列满，即队列中已有M个元素． bool EnCQueue(CyclicQueue& Q, ElemType x){ /* 请编写该函数体 */ }

// 在下面编写函数体

2．已知二又树中的结点类型BinTreeNode定义为： slruct BinTreeNode {char data; BinTreeNode * left, * right;};

其中data为结点值域，left和righ~分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点

总数的递归算法，该总数值由函数返回．假定BT初始指向这棵二叉树的根结点．

int BTreeCount(BinTreeNode* BT);

试题答案及评分标准

六，算法设计题(2小题，每小题6分，共12分) 1．分步给分

if (Q.rear==Q.front && Q.tag== 1) return false; Q.elem[Q.rear] = x; Q.rear = (Q.rear+ 1) % M; if(Q.rear == Q. front) Q.tag= 1; return true; 2．分步给分

int BTreeCount(BinTreeNode * BT) {

if(BT== NULL) return O; else

return BtreeCount(BT->left)+BTreeCount(BT->right)+ l; }