数据结构讲义本科课件试题2009final

1、西 安 电 子 科 技 大 学时间分钟试题1.形式：闭卷；2。日期：20 年 月日 3.本试卷共 四 大题，满分 100 分。班级学号 任课教师 一. 选择题（15 小题，共 30 分）1. 逻辑上通常可以将数据结构分为（A.动态结构和静态结C.线性结构和非线性结构）.顺序结构和链式结构D.初等结构和组合结构2. 在下列对顺序表进行的操作中，算法时间复杂度为 O(1)的是（A.第 i 个元素的前驱（1< i £ n ）后一个新元素(1£ i £ n )B.在第 i 个元C.删除第 i 个元素(1£ i £ n ) D.对顺序表中元素进行排

2、序3. 一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i（1<=i<=n）个元素是（A. 不确定4. 如果将矩阵）。B. n-i+1C.iD. n-iAn× n的每一列看成一个子表，整个矩阵看成是一个广义表 L，即L=(a11,a21,an1),( a12,a22,an2),，（a1n,a2n,ann）),并且可以通过求表头 head 和求表尾 tail 的运算求取矩阵中的每一个元素，则求得 a21 的运算是（）A. head (tail (head (L)C. tail (head (tail (L)B. head (head(head(L)D.

3、head (head (tail (L)第1页 共 页题号一二三四五六七十总分分数第2页 共 页5. 设森林 F 中有三棵树，第一、第二、第三棵树的结点个数分别为 M1，M2 和 M3，则与森林 F 对应的二叉树根结点的右子树上的结点个数是（）。AM1BM1+M2CM3DM2+M36. 对下列关键字序列进行快速排序时，所需进行比较次数最少的是（）A.（1，2，3，4，5，6，7，8） C.（4，3，8，6，1，7，5，2）7. 以下程序的时间复杂度为（for（i=0；i<m；i+） for（j=0；j<t；j+）cij=0； for（i=0；i<m；i+）for（j=0；j&

4、lt;t；j+）for（k=0；k<n；k+）B.（8，7，6，5，4，3，2，1）D.（2，1，5，4，3，6，7，8）cij=cij+aik*bkj；A.O（m+n×t）C.O（m×n×t）B.O（m+n+t）D.O（m×t+n）8.对一棵有 100 个结点的完全二叉树按层序编号，则编号为 49 的结点，它的左孩子的编号为（A.99 C.97）B.98D.509.A. 3C. 5的有向无环图可以得到的拓扑序列的个数是（B. 4D. 6）10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵，则从顶点v0 出发进行深度优先遍

5、历可能得到的顶点A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4，v5，v2，v3)序列为()11.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）A.排序B. 冒泡排序D. 归并排序C. 快速排序12.已知栈的最大容量为 4。若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行,则

6、可能出现的出栈序列为（A.5，4，3，6，1，2 C.3，2，5，4，1，6）B.2，3，5，6，1，4 D.1，4，6，5，2，313.在长度为32 的有序表中进行二分查找时，所需进行的关键字比较次数最多为()A. 4C. 6B.5D.714.定义二维数组 A18，010，起始地址为 LOC，每个元素占 2L 个单元，在以行序为主序的方式下，某数据元素的地址为 LOC+50L，则在以列序为主序的方式下，该元素的A. LOC+28LC. LOC+50L地址为（）B. LOC+36LD. LOC+52L15已知串 s=aabacbabcaccab，串 t1=abc,串 t2=cba,函数 ind

7、ex(s,t)的返回值为串 t 在串 s 中首次出现的位置，则能求得串abcacba的操作序列为（ 注：所有与位置相关的值都从 0 开始计数A. substr (s1,s,6,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s1,s2);B. substr (s1,s,7,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s2,s1);C. substr(s1,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s1,s2);D. substr(s1,

8、s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s2,s1);）第3页 共 页第4页 共 页二. 填空题（10 小题，共 20 分）1. 已知串 S=aaaaba,则 KMP 算法的 Next 数组值为。2. 设某算法的计算时间可用递推关系式 T(n) = 2T(n/2) + n 表示，则该算法的时间复杂度为。3.已知指针p 和 q 分别指向某单链表中第一个结点和最后一个结点。假设指针 s 指向另一个单链表中某个结点，则在 s 所指结点之后为。上述链表应执行的语句4.冒泡排序最好的时间复杂度为，平均时间复杂度为，是一种稳定的排序算法。5.已

9、知循环队列的空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是。6. n 个顶点且含有环路的无向连通图中，至少含有条边。7. 从空树起，依次关键字 1l，27，35，48，52，66 和 73 构造所得的二叉排序树，在等概率查找的假设下，查找时的平均查找长度为。 8用希尔排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时， 增量为 3 的一趟排序的结果为。9.已知一组关键字为15，36，28，97，24，78，47，52，13，86，其中每相邻两个关键字 个有序子序列。 对这些子序列

10、进行一趟两两归并的结果是 。10.假设一棵完全二叉树含 1000 个结点,则其中度为 2 的结点数为。三. 简答题（4 小题，共 30 分）1.(6 分)由森林转换得到的对应二叉树序序列。，写出原森林中第三棵树的前序序列和后ABELCFGKDHIJ2.(9 分)假定一个待散列的线性表为（32，75，63，48，94，25，36，18，70），散列地址空间为0.10，若散列函数为 H(key)=key%11，并采用拉链法处理，试给出它们对应的散列表。并计算等概率查找情况下查找度。和查找失败的平均查找长3.(6 分)设有向图邻接表定义如下；typedef structVertexNode adjl

11、istMax VertexNum;int n,e;ALGraph;/图的当前顶点数和弧数/邻接表类型其中顶点表结点 VertexNode 结构为：边表结点 EdegNode 结构为：阅读下列算法 f，并回答问题： (1)已知有向图 G 的邻接表(2)简述算法 f 的功能。void dfs (ALGraph *G,int v) EdgeNode * p; visitedv=TRUE;,写出算法 f 的输出结果;printf(%c,G>adjlistv·vertex);for(p =G>adjlistv)·firstedge; p; p=p>next) if(

12、! visitedp>adjvex) dfs (G, p>adjvex);void f (ALGraph *G)第5页 共 页adjvexnextvertexfirstedge第6页 共 页int v,w;for(v=0; v <G>n; v +) for(w=0;w<G>n; w+)visitedw=FALSE; printf(%d: ,v);dfs(G,v);printf(n);4(9 分)已知序列（21,41, 7, 43, 58, 63, 29, 8）(1) 写出增量为 3 的第一趟希尔排序结果；(2) 写出以第一元素为枢轴的快速排序第一趟结果；(3

13、)该序列是否为堆。若不是，将其调整为小顶堆，画出调整完的小顶堆。四算法设计题（2 小题，共 20 分）1.(10 分)假设以单链表表示线性表,单链表的类型定义如下: typedef struct node DataType data; struct node *next; LinkNode, *LinkList;编写算法,将一个头指针为 head 且不结点的单链表改造为一个含头结点且头指针仍为 head 的单向循环链表，并分析算法的时间复杂度。2. (10 分)假设二叉排序树以中序后继线索链表作为结构，编写按非递减顺序输出该二叉排序树中所有大于 a 且小于b 的关键字的算法，并分析算法的时间复杂度。相关数据结构定义如下/元素类型typedef structint key;/关键字InfoTyp