当前位置: 首页 > >

09级计科本科数据结构期末考试复*资料

一、选择题 1. 计算机内部数据处理的基本单位是( A.数据 B.数据元素 ) 。 B.数据类型 2. 数据结构是指(

) 。 D.数据库 D.数据定义

C.数据项

A.数据元素的组织形式 3. 设有一个递归算法如下

C.数据存储结构

int fact(int n) { //n 大于等于 0 if(n<=0) return 1; else return n*fact(n-1); } 则计算 fact(n)需要调用该函数的次数为( A.n B.n+1 int X ( int n ) { if ( n<=3 ) return 1; else return X(n-2)+X(n-4)+1; } 试问计算 X(X(5))时需要调用( )次 X 函数。 A.2 B.3 )。 B. (front+l)%n= = rear D.(rear+l)%n= = front ) 。 B.front+l= rear D.(rear+l)%n= front C.4 D.5 5. 在具有 n 个单元的顺序存储的循环队列中, 假定 front 和 rear 分别为队头指针和队尾指针, 则判断队满的条件为( A.rear%n= = front C.rear%n -1= = front 则判断队空的条件为( A.rear%n= = front C.rear= = front 为( ) 。 B.p=p->next; D.p->next=p; )。 B.B, C, D, E, A D.E, D, C, B, A ) 。 B. 模式匹配 C. 串替换 D. 串连接 C.n+2 4. 设有一个递归算法如下 )次。 D.n-1

6. 在具有 n 个单元的顺序存储的循环队列中, 假定 front 和 rear 分别为队头指针和队尾指针,

7. 设单链表中指针 p 指向结点 m,若要删除 m 之后的结点(若存在) ,则需修改指针的操作 A.p->next=p->next->next; C.p=p->next->next; A.A, B, C, D, E C.E, A, B, C, D A. 求子串

8. 设有一个栈,元素的进栈次序为 A, B, C, D, E,下列是不可能的出栈序列(

9. 设有两个串 t 和 p,求 p 在 t 中首次出现的位置的运算叫做(

10. 若 REPLACE(S,S1,S2)表示用字符串 S2 替换字符串 S 中的子串 S1 的操作,则对 于 S=“Beijing&Nanjing”,S1=“Beijing”,S2=“Shanghai”,REPLACE(S,S1,S2)=( ) 。 A. “Nanjing&Shanghai” C. “ShanghaiNanjing” A.LOC(a00)+[j*m+i] B. “Nanjing&Nanjing” D. “Shanghai&Nanjing” ) 。 B. LOC(a00)+[j*n+i]

11. 若数组 A[0…m][0…n]按列优先顺序存储,则 aij 地址为(

C.LOC(a00)+[(j-1)*n+i-1] 址为( A.520 A.无穷大 A.x A. 不发生改变 C. 不能确定 ) 。 B.522 B.3 B.(a,B)

D. LOC(a00)+[(j-1)*m+i-1]

12. 已知二维数组 A10×10 中,元素 a20 的地址为 560,每个元素占 4 个字节,则元素 a10 的地 C.524 C.2 C.(x,(a,B)) D.A ) 。 D.518 ) 。 D.5 ) 。

13. 设有广义表 D=(a,b,D),其长度为( ) ,深度为(

14. 广义表 A=((x,(a,B)),(x,(a,B),y)),则运算 head(head(tail(A)))的结果为(

15. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序( B. 发生改变 D. 以上都不对 ) 。 D. R[2i-1]

16. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中 R[1..n],结点 R[i]若有 左孩子,其左孩子的编号为结点( A. R[2i+1] 为( A. 3 为( A. 20 A. n ( )。 A. O(n) A. -1?1 杂度大致为( A. O(n) B. O(1) B. -2?2 )。 B. O(1) C. O(log2n) D. O(n2) C. O(log2n) C. 1?2 D. 0?1 D. O(n2) )。 )。 B. 4 )的 9 分之一。 B. 18 B. n+1 C. 25 C. n-1 D. 22 D. 2n C. 5 D. 6 B. R[2i] C. R[i/2]

17. 对于长度为 18 的顺序存储的有序表,若采用折半查找,则查找第 15 个元素的比较次数

18. 对于长度为 9 的顺序存储的有序表,若采用折半查找,在等概率情况下的*均查找长度

19. 在对 n 个元素进行直接插入排序的过程中,共需要进行(10. C)趟。 20. 从具有 n 个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为

21. 在一棵 AVL 树中,每个结点的*衡因子的取值范围是(

21. 从具有 n 个结点的 AVL 树中搜索一个元素时,在等概率情况下进行成功搜索的时间复

二、填空题 1. 下面程序段的时间复杂度是__________________。 i=1; while(i<=n) i=i*3; 2. 下面程序段的时间复杂度是__________________。 i=s=0; while(s<n) { i++; s+=i; }

3. 根据线性表的链式存储结构中每个结点所含指针的个数,链表可分为_________和 _______;而根据指针的联接方式,链表又可分为________和_________ 4. 在单链表中设置头结点的作用是________和______ 。 5. 设字符串 S1= “ABCDEF”,S2= “PQRS”,则运算 S=CONCAT(SUB(S1,2,LEN(S2), ) SUB(S1,LEN(S2) )后的串值为___________________ ,2) 6. 在双向链表中,每个结点含有两个指针域,一个指向_______结点,另一个指向_______ 结点。 7. 数组 A[1…10,-2…6,2…8]以行优先的顺序存储,设第一个元素的首地址是 100,每个 元素占 3 个存储长度的存储空间,则元素 A[5,0,7]的存储地址为______________。 8. 一 个 n×n 的 对 称 矩 阵 , 如 果 以 行 为 主 序 或 以 列 为 主 序 存 入 内 存 , 则 其 容 量 为 ______________。 9. 已知广义表 A=((a,b,c),(d,e,f)),则运算 head(tail(tail(A)))=____________。 10. 一个广义表为(a,(a,b),d,e,((i,j),k)),则该广义表的长度为_____,深度为_____。 11. 若一个连通图中每个边上的权值均不同, 则得到的最小生成树是________ 唯一/不唯一) ( 的。 12. 三叉链表比二叉链表多一个指向______________的指针域。 13. 以折半查找方法在一个查找表上进行查找时,该查找表必须组织成________存储的 ________表。 14. 根据图的存储结构进行某种次序的遍历,得到的顶点序列是__(唯一/不唯一)的。 15. 在时间复杂度为 O(nlog2n)的所有排序方法中,________排序方法是稳定的。 16. 对一棵二叉排序树进行中序遍历时,得到的结点序列是一个________。 17. 在时间复杂度为 O(n2)的所有排序方法中,________排序方法是不稳定的。 三、应用题 1. 假设一棵二叉树的后序序列为 DCEGBFHKJIA,中序序列为 DCBGEAHFIJK,请写出该 二叉树的先序遍历序列。 2.假设一棵二叉树的先序序列为 EBADCFHGIKJ,中序序列为 ABCDEFGHIJK,请写出该二 叉树的后序遍历序列。 3. 已知一个无向图的邻接矩阵如图 1 所示,试写出从顶点 0 出发分别进行深度优先和广度 优先搜索遍历得到的顶点序列。

图1

4. 已知一个无向图的邻接表如图 1 所示,试写出从顶点 0 出发分别进行深度优先和广度优 先搜索遍历得到的顶点序列。

5. 图 2 所示为一个有向网图及其带权邻接矩阵, 要求对有向图采用 Dijkstra 算法, 求从 V0 到 其余各顶点的最短路径。

100 V0 30

V5

60 V4 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ 20 ∞ 30 ∞ ∞ ∞ ∞ ∞ 100 ∞ ∞ 10 60 ∞

10 V1 5 V2

10

20

50

V3

(a) 有向带权图 图 2 有向带权图及其邻接矩阵

(b) 带权邻接矩阵

6. 对于下图 G,试给出一种*诵蛄校粼谒牧诮颖泶娲⒔峁怪校扛龆サ懔诮颖碇械 边结点都是按照终点序号从大到小链接的,则按此给出唯一一种*诵蛄小

2 0 3 1 4 6 8 5 7 9

7. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72),画出按线性表中元素的次序生成的一 棵二叉排序树,求出其*均查找长度。 8. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76),试画出对应的折半查找判 定树,求出其*均查找长度。 9. 已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用归并排序法进行排序时每一趟 的排序结果。 10.已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序时每一趟 的排序结果。

四、读程序填空题 1.在单链表的开始点之前插入一新结点。 Void Deamol (LinkList *head.DataType x) {//*head 为不带头结点的单链表 ListNode *u; u=(ListNode *)malloc (sizeof(ListNode) ); u->date=x; ______(1)_______; ______(2)_______; } 2.下列为在单链表中删除一个结点的算法。 Void Demo2(LinkList head,ListNode * p) { //head 是带头结点的单链表,删除 p 指向的结点 ListNode * q=head; While ( q && __(1)___ ) q=q->next; if q error(“*p not in head”); __(2)__; __(3)__; }

3.下列函数是按从小到大的次序输出二叉排序树的各结点。 Void order(BinTree T) { if (___(1)___) {___(2)___; printf(“%d”,T->data); ____(3)____; }

}

4.下列函数是按从小到大的次序输出二叉排序树的各结点。 Void order(BinTree T) { if (___(1)___) {___(2)___; printf(“%d”,T->data); ____(3)____; } }

5.已知奇偶转换排序如下所述:第一趟对所有奇数的 i,将 a [ i ]和 a[i+1]进行比较,第二趟 对所有偶数的 i ,将 a[i]和 a[ i +1]进行比较,每比较时若 a[ i ] > a [i+1] ,则将两者交换, 以后重复上述两趟过程交换进行,直到整个数组有序请完善下列程序。 Void oesort ( int a[ n ] ) { int i ,flag ; do { flag =0 ; for ( i =1 ; i < n ; i ++,i ++ ) if ( a[ i ] >a [ i +1] ) { ______(1)_____; t = a [ i + 1 ]; a [i +1 ] = a [ i ]; a [ i ]= t ; } for ( ____(2)______) flag = 1 ; t = a [i +1]; a [ i + 1 ] = a [i ]; a [ i ] = t; } } while (___(4)_________); } 6. 直接插入排序 void insertsort(int R[ ] ) // 按递增序对 R[1]~ R[ n ]进行直接插入排序 { int i, j; for ( i=2; i <= ______ ; i++ ) / * 偶数扫描 */ if (____(3)_________) { /* 奇数扫描 */

{ R [ 0 ]=R[ i ]; j= ______ ;

// 设定 R[0]为监视哨

while (R[ 0 ] ______ R[ j ] ) {______ j- - ; } R[ j+1 ]= ______ ; } } 7.先序遍历二叉树 设二叉树用二叉链表表示,以 t 为根指针,二叉链表结点的类型为 node;栈 s 的元素类型 为指向 node 的指针类型, 栈容量 M 足够大。先序遍历的非递归算法如下: struct node {char data; node *lc,*rc; }; void preorder (node *t) { node *s[ M ] ,*p=______ ; int top=- 1; do { while (p!=NULL) { ______ ____________ } if (top!= -1) {p=s[top- -]; ____________; } } while (( top! = - 1 ) || ( p ! =NULL )); } ; ; s[++top] = ______ ; //置栈空; // 插入第 i 个记录 ;

五、算法设计题 1. 已知线性表的元素是无序的,且以带头结点的单链表作为存储结构。设计一个删除表中 所有值小于 max 但大于 min 的元素的算法。 2. 已知线性表的元素按递增顺序排列,并以带头结点的单链表作存储结构。试编写一个删 除表中所有值大于 min 且小于 max 的元素(若表中存在这样的元素)的算法。 3. 设顺序表 L 是一个递减有序表,试写一算法,将 x 插入其后仍保持 L 的有序性。 4. 设单链表 L 是一个递减有序表,试写一算法,将 x 插入其后仍保持 L 的有序性。




友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版