当前位置:首页 >> 理学 >>

数据结构试题及答案(2)

数据结构试题 一、 单选题(每题 2 分,共 20 分) 1. 1. 对一个算法的评价,不包括如下( B )方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 2. 2. 在带有头结点的单链表 HL 中, 要向表头插入一个由指针 p 指向的 结点,则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3. 对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4. 一个栈的输入序列为 1 2 3,则下列序列中不可能是栈的输出序 列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5. AOV 网是一种( D ) 。 A.有向图 B.无向图 C.无向无环图 D.有向无环图 6. 6. 采用开放定址法处理散列表的冲突时,其平均查找长度( B ) 。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 7. 7. 若需要利用形参直接访问实参时,应将形参变量说明为( D )参 数。 A.值 B.函数 C.指针 D.引用 8. 8. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点 都具有相同的( A ) 。 A.行号 B.列号 C.元素值 D.非零元素个数 9. 9. 快速排序在最坏情况下的时间复杂度为( D ) 。 A.O(log2n) B.O(nlog2n) C.O(n) D.O(n2) 10. 10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n ) 二、运算题(每题 6 分,共 24 分) 1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在 M 对 N(M:N)的联系时,称这种结构为图(或图结构) 。 2. 2.队列的插入操作是在队列的__队尾___进行,删除操作是在队列的 _对头_ 进行。 3. 3. 当用长度为 N 的数组顺序存储一个栈时,假定用 top==N 表示栈空,则 表示栈满的条件是_top==0__。
2

1

4. 4. 5.

对于一个长度为 n 的单链存储的线性表,在表头插入元素的时间复杂

6. 7. 8.

度为_O(1)_,在表尾插入元素的时间复杂度为__O(n)_。 5. 设 W 为一个二维数组,其每个数据元素占用 4 个字节,行下标 i 从 0 到 7 ,列下标 j 从 0 到 3 ,则二维数组 W 的数据元素共占用_128_个字节。W 中第 6 行的元素和第 4 列的元素共占用_44___个字节。若按行顺序存放二 维数组 W, 其起始地址为 100, 则二维数组元素 W[6, 3]的起始地址为_108__。 6. 广义表 A= (a,(a,b),((a,b),c)), 则它的深度为 __3___ ,它的长度为 __3____。 7. 二叉树是指度为 2 的__有序__树。一棵结点数为 N 的二叉树,其所有结 点的度的总和是__n-1__。 8. 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个__有序序列

__。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是 该算术表达式的__后缀表达式_。 9. 9. 对于一棵具有 n 个结点的二叉树,用二叉链表存储时,其指针总数为 ___2n____个,其中__n-1__个用于指向孩子,__n+1__个指针是空闲的。 10. 10.若对一棵完全二叉树从 0 开始进行结点的编号,并按此编号把它顺序存 储到一维数组 A 中,即编号为 0 的结点存储到 A[0]中。其余类推,则 A[ i ] 元 素 的 左 孩 子 元 素 为 ___2i+1, 右 孩 子 元 素 为 __2i+2__ , 双 亲 元 素 为 _(i-1)/2__。 11. 11.在线性表的散列存储中,处理冲突的常用方法有_开放地址法__和__链接 法__两种。 12. 12.当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用 __快速___排序;当待排序的记录数较大,存储空间允许且要求排序是稳定 时,宜采用__归并__排序。 三、运算题(每题 6 分,共 24 分) 1. 1. 已知一个 6?5 稀疏矩阵如下所示,
?0 ?0 ? ?0 ? ?0 ?5 ? ?0 ? 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 1 ? 0 ? ? 0 ? ? ? 2? 0 ? ? 0 ? ?

?1 0

试: (1)写出它的三元组线性表; (2)给出三元组线性表的顺序存储表示。 2. 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空 树起,逐个输入各个数据而生成的二叉搜索树。 3. 3. 对于图 6 所示的有向图若存储它采用邻接表,并且每个顶点邻接表中的

2

边结点都是按照终点序号从小到大的次序链接的,试写出: (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树; (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树; 4. 4. 已知一个图的顶点集 V 和边集 E 分别为: V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4 ,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2 >,<6,5>}; 若存储它采用邻接表, 并且每个顶 点邻接表中的边结点都是按照终点序 号从小到大的次序链接的,按主教材

图6

中介绍的拓朴排序算法进行排序,试给出得到的拓朴排序的序列。 四、阅读算法(每题 7 分,共 14 分) 1. 1. int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break;

if (i>x) return 1; else return 0; } (1) (1) 指出该算法的功能; (2) (2) 该算法的时间复杂度是多少? 2. 2. 写出下述算法的功能: void AJ(adjlist GL, int i, int n) { Queue Q; InitQueue(Q); cout<<i<<' '; visited[i]=true; QInsert(Q,i); while(!QueueEmpty(Q)) { int k=QDelete(Q); edgenode* p=GL[k]; while(p!=NULL) {

3

int j=p->adjvex; if(!visited[j]) { cout<<j<<' '; visited[j]=true; QInsert(Q,j); } p=p->next; } } } 五、算法填空(共 8 分) 如下为二分查找的非递归算法,试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) { int low=0; int high=n-1; while (low<=high) { int mid=_______________________________; if (K==A[mid].key) return mid; //查找成功,返回元素的下标 else if (K<[mid].key) ______________________________________; // 在左子表 上继续查找 else __________________________________; // 在右子 表上继续查找 } return -1; //查找失败,返回-1 } 六、编写算法(共 8 分) HL 是单链表的头指针,试写出删除头结点的算法。 ElemType DeleFront(LNode * & HL) 参考答案 三、运算题(每题 6 分,共 24 分) 1. 1. ( 1



4

((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (2)三元组线性表的顺序存储表示如图 7 示。 2. 2. 如图 8 所示。 3. 3. DFS:????? BFS:????? 4. 4. 拓朴排序为: 4 3 6 5 7 2 1 四、阅读算法(每题 7 分,共 14 分)

(3 分)
6 1 3 4 5 6 图7 5 5 2 5 1 3 5 1 -1 -2 5 7

图8 1. 1. (1) 判断 n 是否是素数(或质数) (2)O( n ) 2. 2. 功能为:从初始点 vi 出发广度优先搜索由邻接表 GL 所表示的图。 五、算法填空(8 分) (low+high)/2 high=mid-1 low=mid+1 六、编写算法(8 分) ElemType DeleFront(LNode * & HL) { if (HL==NULL){ cerr<<"空表"<<endl; exit(1); } LNode* p=HL; HL=HL->next; ElemType temp=p->data; delete p; return temp; } 课程测试试题( 1 卷) 一、单选题(每题 2 分,共 20 分) 1. 1. 栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

5

2. 2.

用链接方式存储的队列,在进行插入运算时( D ).

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 3. 以下数据结构中哪一个是非线性结构?( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 4. 设有一个二维数组 A[m][n],假设 A[0][0]存放位置在 644(10), A[2][2]存放位置在 676(10), 每个元素占一个空间, 问 A[3][3](10)存放在什 么位置?脚注(10)表示用 10 进制表示。( C ) A.688 B.678 C.692 D.696 5. 5. 树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 6. 二叉树的第 k 层的结点数最多为( D ). A.2k-1 B.2K+1 C.2K-1 D. 2k-1 7. 7. 若有 18 个元素的有序表存放在一维数组 A[19]中,第一个元素放 A[1]中,现进行二分查找,则查找 A[3]的比较序列的下标依次为( D ) A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 8. 8. 对 n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 ( C ) A. O(1) B. O(n) C. O(1og2n) D. O(n2) 9. 9. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时, 若选用 H(K)=K %9 作为散列函数,则散列地址为 1 的元素有( D )个, A.1 B.2 C.3 D.4 10. 10. 设有 6 个结点的无向图,该图至少应有( A )条边才能确保是一个连 通图。 A.5 B.6 C.7 D.8 二、填空题(每空 1 分,共 26 分) 1. 1. 通常从四个方面评价算法的质量:_正确性_、_易读性_、_强壮性_和_ 2. 3. 4. 5. 高效率_。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为_ O(n)_。 3. 假定一棵树的广义表表示为 A(C,D(E,F,G) ,H(I,J) ) ,则树中所 含的结点数为_9__个,树的深度为_3_,树的度为_3_。 4. 后缀算式 9 2 3 +- 10 2 / -的值为__-1__。中缀算式(3+4X)-2Y/3 对应的后缀算式为_ 3 4 X * + 2 Y * 3 / -_。 5. 若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和 右孩子的两个指针。在这种存储结构中,n 个结点的二叉树共有_ 2n _个指

6

针域,其中有_ n-1_个指针域是存放了地址,有__ n+1__个指针是空指针。 6. 6. 对于一个具有 n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表 中,所含边结点分别有__e__个和_2e _个。 7. 7. AOV 网是一种___有向无回路___的图。 8. 8. 在一个具有 n 个顶点的无向完全图中,包含有__ n(n-1)/2 _条边,在 一个具有 n 个顶点的有向完全图中,包含有_ n(n-1)_条边。 9. 9. 假定一个线性表为(12,23,74,55,63,40),若按 Key % 4 条件进行划分, 使得同一余数的元素成为一个子表,则得到的四个子表分别为__(12,40) __、__( )__、_(74) __和__(23,55,63)__。 10. 10. 向一棵 B_树插入元素的过程中,若最终引起树根结点的分裂,则新 树比原树的高度__增加 1_。 11. 11. 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为 _ O(log2n)_,整个堆排序过程的时间复杂度为_ O(nlog2n)_。 12. 12. 在快速排序、堆排序、归并排序中, _归并_排序是稳定的。 三、运算题(每题 6 分,共 24 分) 1. 1. 在如下数组 A 中链接存储了一个线性表, 表头指针为 A [0].next, 试写出该线性表。 A 0 1 2 3 4 5 6 7 data next 3 60 5 50 7 78 2 90 0 34 4 40 1

2. 2. 3. 3. 为:

请画出图 10 的邻接矩阵和邻接表。 已知一个图的顶点集 V 和边集 E 分别

V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4) 图 10 15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树, 试写出在最小生成树中依次得到的各 条边。 4. 4. 画出向小根堆中加入数据 4, 2, 5, 8, 3 时,每加入一个数据后 堆的变化。 四、阅读算法(每题 7 分,共 14 分) 1. 1. LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L->next){ q=L;L=L->next;p=L;

7

S1: S2:

while(p->next) p=p->next; p->next=q;q->next=NULL; } return L;

} 请回答下列问题: (1)说明语句 S1 的功能; (2)说明语句组 S2 的功能; (3)设链表表示的线性表为(a1,a2, ?,an),写出算法执行后的返回值 所表示的线性表。 2. 2. void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout<<BT->data<<' '; } } 该算法的功能是: 五、算法填空(共 8 分) 二叉搜索树的查找——递归算法: bool Find(BTreeNode* BST,ElemType& item) { if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return ___________;} else if(item<BST->data) return Find(______________,item); else return Find(_______________,item); }//if } 六、编写算法(共 8 分) 统计出单链表 HL 中结点的值等于给定值 X 的结点数。

8

int CountX(LNode* HL,ElemType x) 参考答案 三、运算题(每题 6 分,共 24 分) 1. 1. 线性表为: (78,50,40,60,34,90) ?0 1 1 1 0 ? ?1 0 1 0 1 ? ? ? ?1 1 0 1 1 ? ? ? ?1 0 1 0 1 ? ? ? 2. 2. 邻接矩阵: ?0 1 1 1 0? 邻接表如图 11 所示:

图 11 3. 3. 用克鲁斯卡尔算法得到的最小生成树为: (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 4. 见图 12
4 2 4 4 2 4 2 5 8 2 3 8 4 5 4 2 5 8 4 3 2 5

图 12 四、阅读算法(每题 7 分,共 14 分) 1. 1. (1)查询链表的尾结点 (2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,?,an,a1) 2. 2. 递归地后序遍历链式存储的二叉树。 五、算法填空(每空 2 分,共 8 分) true BST->left BST->right 一、 六、 编写算法(8 分)

9

int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i 为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时 i 中的值即为 x 结点个数 return i; }//CountX

课程测试试题(2 卷) 一、单选题(每小题 2 分,共 8 分) 1、1、 在一个长度为 n 的顺序线性表中顺序查找值为 x 的元素时,查找成功时的 平均查找长度(即 x 与元素的平均比较次数,假定查找每个元素的概率 都相等)为 ( C )。 A n B n/2 C (n+1)/2 D (n-1)/2 2、2、 在一个单链表中,若 q 所指结点是 p 所指结点的前驱结点,若在 q 与 p 之间 插入一个 s 所指的结点,则执行( D )。 A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 3、 栈的插入和删除操作在( A )进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4、 4、 由权值分别为 11,8,6,2,5 的叶子结点生成一棵哈夫曼树, 它的带权路径长度为( B ) A 24 B 71 C 48 D 53 二、填空题(每空 1 分,共 32 分) 5、1、数据的逻辑结构被分为___集合____、 ___线性______ 、___树_____ 和___图_____四种。 6、2、一种抽象数据类型包括_数据描述____和_操作声名___两个部分。 7、3、在下面的数组 a 中链接存储着一个线性表,表头指针为 a[o].next, 则该线性表为_(38,56,25,60,42,74) 。 a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 8、4、在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中,判

10

断链表为空的条件分别为_HL→next =NULL__和_ HL=HL→next _。 9、5、用具有 n 个元素的一维数组存储一个循环队列,则其队首指针总是指 向队首元素的_前一个位置__,该循环队列的最大长度为__ n-1__。 10、 6、 当堆栈采用顺序存储结构时, 栈顶元素的值可用 S.stack [S.top] 表示; 当堆栈采用链接存储结构时,栈顶元素的值可用_HS→data _表示。 11、 7、一棵高度为 5 的二叉树中最少含有_5_个结点,最多含_31_个结 点。 12、 8、在图的邻接表中,每个结点被称为_边结点__,通常它包含三个 域:一是_邻接点域__;二是__权域___;三是__链域__。 13、 9、在一个索引文件的索引表中,每个索引项包含对应记录的_索引 值域_和_开始位置域_两项数据。 14、 10、 假定一棵树的广义表表示为 A(B (C,D(E, F,G) , H(I,J) ) ) ,则树中所含的结点数为_10__个,树的深度为__3__,树的度 为_3_, 结点 H 的双亲结点为__B___,孩子结点为_I 和 J _ 。 15、 11、 在堆排序的过程中,对任一分支结点进行筛运算 的 时 间 复 杂 度 为 _O ( log2n ) _, 整 个 堆 排 序 过 程 的 时 间 复 杂 度 为 _ O(nlog2n)_。 16、 12、 在对 m 阶的 B_树插入元素的过程中,每向一个结 点插入一个索引项(叶子结点中的索引项为关键字和空指针)后,若该 结点的索引项数等于_ m _个,则必须把它分裂为_ m - 1__个结点。 三、运算题(每小题 6 分,共 24 分) 17、 1、已知一组记录的排序码为(46,79,56,38,40,80, 写出对其进行快速排序的每一次划分结果。

95,24) ,

18、 2、一个线性表为 B=(12,23,45,57,20,03,78,31,15,36) , 设散列表为 HT[0..12],散列函数为 H(key)= key % 13 并用线性探查 法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找 长度。 19、 3、已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ,中序遍历 的结果是 EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。

4、已知一个图的顶点集 V 各边集 G 如下: V = {0,1,2,3,4,5,6,7,8,9}; E = {(0,1) , (0,4) , (1,2) , (1,7) , (2,8) , (3,4) , (3 ,8) , (5,6) , (5,8) , (5,9) , (6,7) , (7,8) , (8,9)}

20、

11

当它用邻接矩阵表示和邻接表表示时,分别写出从顶点 V0 出发按深度优先 搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。 假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 图 邻接矩阵表示时 邻接表表示时 深度优先序列 广度优先序列

四、阅读算法,回答问题(每小题 8 分,共 16 分) 1、假定从键盘上输入一批整数,依次为:78 写出输出结果。 # include < iostream.h> # include < stdlib.h > consst int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” Void main ( ) { stack a; initstack(a); int x; cin >>x; while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout <<pop (a) <<” ” ; cout <<end1; } 该算法的输出结果为: __________________________________________________________. 63 45 30 91 34 –1,请

12

2、阅读以下二叉树操作算法,指出该算法的功能。 Template <calss type > void BinTree <Type> : : unknown (BinTreeNode<Type>*t) { BinTreeNode< Type> *p =t, *temp; if (p!=NULL) { temp = p→leftchild; p→leftchild = p→rightchild; p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild); } } 该算法的功能是:________________________________

五、算法填空,在画有横线的地方填写合适的内容(10 分) 对顺序存储的有序表进行二分查找的递归算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) { if (low <= high) { int mid = 1 if ( K= = A[ mid ].key ) return mid; else if ( K < A[mid].key) return 2 else return 3 } else return 六、编写算法(10 分) 编写算法, 将一个结点类型为 Lnode 的单链表按逆序链接,即若原单链表中 存储元素的次序为 a1,??an-1,an,则逆序链接后变为, an,an-1,??a1。

4

13

Void

contrary (Lnode * & HL)

数据结构试题(答案) 三、运算题(每小题 6 分,共 24 分) 1、 划分次序 第一次 [38 24 第二次 24 [38 第三次 24 38 第四次 24 38 第五次 24 38 第六次 24 38 2、
0 1 2 3 4 5 6 7 8 9 10 11 12

划分结果 40] 46 [56 80 95 40] 46 [56 80 95 40 46 [56 80 95 40 46 56 [80 95 40 46 56 79 [80 40 46 56 79 80

79] 79] 79] 79] 95] 95

78

15

03

57

45

20

31

23

36

12

查找成功的平均查找长度:ASL SUCC=14/10= 1.4 3、此二叉树的后序遍历结果是:EDCBIHJGFA 4、 图 邻接矩阵表示 时 邻接表表示时 深度优先序列 广度优先序列

0,1,2,8,3,4,5,6,7, 0,1,4,2,7,3,8,6,5, 9 9 0,4,3,8,9,5,6,7,1, 0,4,1,3,7,2,8,6,9, 2 5 四、阅读算法,回答问题(每小题 8 分,共 16 分) 21、 1、 该算法的输入结果是:34 91 30 45 63 78 22、 2、 该算法的功能是:交换二叉树的左右子树的递归算法。 五、算法填空,在画有横线的地方填写合适的内容(10 分) 1、1 是: (low + high)/2; 2 是: Binsch(A,low,mid–1,K); 3 是: Binsch(A,mid+1,high,K); 4 是: -1; 六、编写算法(10 分) 根据编程情况,酌情给分。 { Lnode *P=HL;

14

HL=NULL; While (p!=null) { Lnode*q=p; P=p→next; q→next=HL; HL=q; } } 课程测试试题(卷) 第一部分 选择题(30 分)

一、项选择题 1.算法指的是( D ) A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列 2.线性表采用链式存储时,结点的存储地址( B ) A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续 3. 将长度为 n 的单链表链接在长度为 m 的单链表之后的算法的时间复杂度为 (C) A.O(1) B.O(n) C.O(m) D.O(m+n) 4.由两个栈共享一个向量空间的好处是: (B ) A.减少存取时间,降低下溢发生的机率 B.节省存储空间,降低上溢发生的机率 C.减少存取时间,降低上溢发生的机率 D.节省存储空间,降低下溢发生的机率 5.设数组 data[m]作为循环队列 SQ 的存储空间,front 为队头指针,rear 为队 尾指针,则执行出队操作后其头指针 front 值为(D) A.front=front+1 B.front=(front+1)%(m-1) C.front=(front-1)%m D.front=(front+1)%m 6.如下陈述中正确的是( A ) A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串 7.若目标串的长度为 n,模式串的长度为[n/3],则执行模式匹配算法时,在最 n 坏情况下的时间复杂度是( C ) A.O( 3 ) B.O(n) C.O(n2) D.O(n3) 8.一个非空广义表的表头( D ) A.不可能是子表 B.只能是子表

15

? 0 ?8 0 6? ? 0 ?8 0 6 ? ? 7 0 0 0? ? 9.假设以带行表的三元组表表示稀疏矩阵,则和下列行表 0 0 ?8 00 0? 6? ?7 ? ? ? 0 ?8 0 6? ? ?? ? 0 0 20 30 3 0? 5 5 00 4 0 0? A. ? 0 B. ? ??0 ? 0 0 0 0? ? ?? ?0 7 00 00 0? 0? 0 4 D.? 对应的稀疏矩阵是( A ) 05 2 0 0 0? C. ? ? ? ? ? 0 0 0 0? ? 0 5 30 04 0? 0? ??5 0 4 0? ? ? ?? ? ? ? ? ? 0 3 0 0? ? ? 0 0 0 0? ?

C.只能是原子

D.可以是子表或原子

10.在一棵度为 3 的树中,度为 3 的结点个数为 2,度为 2 的结点个数为 1,则度 为 0 的结点个数为( C ) A.4 B.5 C.6 D.7 11.在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为( D ) A.e B.2e C.n -e D.n -2e 12.假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示,则删除与某个顶点 vi 相关的所有弧的时间复杂度是( C ) A.O(n) B.O(e) C.O(n+e) D.O(n*e) 13.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进 行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是(D) A.选择排序 B.希尔排序 C.归并排序 D.快速排序 14.适于对动态查找表进行高效率查找的组织结构是(C) A.有序表 B.分块有序表 C.三叉排序树 D.线性链表 15.不定长文件是指(B) A.文件的长度不固定 B.记录的长度不固定 C.字段的长度不固定 D.关键字项的长度不固定 第二部分 非选择题(共 70 分) 二、填空题(本大题共 10 小题,每小题 2 分,若有两个空格,每个空格 1 分, 共 20 分)不写解答过程,将正确的答案写在每小题的空格内。错填或不填 均无分。 16.数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储(或存储结构) 无关,是独立于计算机的。 17.在一个带头结点的单循环链表中,p 指向尾结点的直接前驱,则指向头结点 的指针 head 可用 p 表示为 head= p->next->next。 18.栈顶的位置是随着进栈和退栈操作而变化的。 19.在串 S=“structure”中,以 t 为首字符的子串有 12 个。 20. 假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中,其中
2 2

16

B[0]存储矩阵中第 1 个元素 a1,1,则 B[31]中存放的元素是

a4,8



21.已知一棵完全二叉树中共有 768 结点,则该树中共有 384 个叶子结点。 22.已知一个图的广度优先生成树如右图所示,则与此相 应的广度优先遍历序列为 Abefcdg 。

23.在单链表上难以实现的排序方法有快速排序和堆排序。 24.在有序表(12,24,36,48,60,72,84)中二分查找关键字 72 时所需进 行的关键字比较次数为 2 。 25.多重表文件和倒排文件都归属于 多关键字 文件。 三、解答题(本大题共 4 小题,每小题 5 分,共 20 分) 26.画出下列广义表的共享结构图形表示 P=( ( (z),(x,y)),((x,y),x),(z)) 27.请画出与下列二叉树对应的森林。

?01001? ?10010? ? ? ?00011? ? ? 28.已知一个无向图的顶点集为 {a, ?01101? ? ? 10110 ? ? a

b, c, d, e} ,其邻接矩阵如下所示

(1)画出该图的图形; b (2)根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历, c d 写出相应的遍历序列。 e 29.已知一个散列表如下图所示: 35 20 33 48 59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数为 h(key)=key%13, 处理冲突的方法为双重散列法, 探查序列为: i =0,1,?,m-1 hi=(h(key)+ i *h1(key))%m 其中 h1(key)=key%11+1 回答下列问题: (1)对表中关键字 35,20,33 和 48 进行查找时,所需进行的比较次数各 为多少? (2)该散列表在等概率查找时查找成功的平均查找长度为多少? 四、算法阅读题(本大题共 4 小题,每小题 5 分,共 20 分) 30.下列算法的功能是比较两个链串的大小,其返回值为:

17

comstr(s1,s2)=

??1 当s1 ? s2 ? ? 0 当s1 ? s2 ? 1 当s ? s 1 2 ?

请在空白处填入适当的内容。 int comstr(LinkString s1,LinkString s2) {//s1 和 s2 为两个链串的头指针 while(s1&&s2){ if(s1->date<s2->date)return-1; if(s1->date>s2->date)return1; ① ; ② ; } if( ③ )return-1; if( } 31.阅读下面的算法 LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L->next){ q=L;L=L->next;p=L; S1: while(p->next) p=p->next; S2: p->next=q;q->next=NULL; } return L; ④ ⑤ )return1; ;

} 请回答下列问题: (1)说明语句 S1 的功能; (2)说明语句组 S2 的功能; (3)设链表表示的线性表为(a1,a2, ?,an),写出算法执行后的返回值 所表示的线性表。 32.假设两个队列共享一个循环向量空间(参见右 下图) , 其类型 Queue2 定义如下: typedef struct{ DateType data[MaxSize]; int front[2],rear[2]; }Queue2; 对于 i=0 或 1,front[i]和 rear[i]分别为第 i 个队列的头指针和尾指针。 请对以下算法填空,实现第 i 个队列的入队操作。

18

int EnQueue (Queue2*Q,int i,DateType x) {//若第 i 个队列不满,则元素 x 入队列,并返回 1;否则返回 0 if(i<0||i>1)return 0; if(Q->rear[i]==Q->front[ ① ]return0; Q->data[ ② ]=x; Q->rear[i]=[ ③ ]; return1; } 33.已知二叉树的存储结构为二叉链表,阅读下面算法。 typedef struct node { DateType data; Struct node * next; }ListNode; typedef ListNode * LinkList ; LinkList Leafhead=NULL; Void Inorder (BinTree T) { LinkList s; If(T){ Inorder(T->lchild); If ((!T->lchild)&&(!T->rchild)){ s=(ListNode*)malloc(sizeof(ListNode)); s->data=T->data; s->next=Leafhead; Leafhead=s; } Inorder(T->rchild); } } 对于如下所示的二叉树

(1)画出执行上述算法后所建立的结构; (2)说明该算法的功能。 五、算法设计题(本题共 10 分) 34.阅读下列函数 arrange() int arrange(int a[],int 1,int h,int x)

19

{//1 和 h 分别为数据区的下界和上界 int i,j,t; i=1;j=h; while(i<j){ while(i<j && a[j]>=x)j--; while(i<j && a[j]>=x)i++; if(i<j) { t=a[j];a[j]=a[i];a[i]=t;} } if(a[i]<x) return i; else return i-1; } (1)写出该函数的功能; (2)写一个调用上述函数实现下列功能的算法:对一整型数组 b[n]中的元素 进行重新排列,将所有负数均调整到数组的低下标端,将所有正数均调整 到数组的高下标端,若有零值,则置于两者之间,并返回数组中零元素的 个数。 数据结构试题参考答案 三、解答题(本大题共 4 小题,每小题 5 分,共 20 分) 26.

图1 27.

图2

28.该图的图形为:

20

深度优先遍历序列为:abdce 广度优先遍历序列为:abedc 29. (1)对关键字 35、20、33 和 48 3? 2? 1 ?进行查找的比较次数为3、2、1、1; 1? 2 9 ASL ? ? 5 5 (2)平均查找长度 四、算法阅读题(本大题共 4 小题,每小题 5 分,共 20 分) 30. ①S1=S1->next ②s2=s2->next ③s2(或 s2!=NULL 或 s2&&!s1) ④s1(或 s1!=NULL 或 s1&&!s2) ⑤return 0 31.(1)查询链表的尾结点 (2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,?,an,a1) 32. ①(i+1)%2(或 1-i) ②Q->rear[i] ③(Q->rear[i]+)%Maxsize 33.(1)Leafhead F H G D ∧ ( 2 )中序遍历二叉树,按遍历序列中叶子结点数据域的值构建一个以 Leafhead 为头指针的逆序单链表(或按二叉树中叶子结点数据自右至 左链接成一个链表) 。 五、算法设计题(本题共 10 分) 34. (1)该函数的功能是:调整整数数组 a[]中的元素并返回分界值 i,使所 有<x 的元素均落在 a[1..i]上, 使所有≥x 的元素均落在 a[i+1..h] 上。 (2)int f(int b[],int n) 或 int f(int b[],int n) { { int p,q; int p,q; p=arrange(b,0,n-1,0); p=arrange(b,0,n-1,1); q= arrange(b,p+1,n-1,1); q= arrange(b,0,p,0); return q-p; return p-q; } } 课程测试试题(3 卷) 一、选择题(20 分)

21

1.组成数据的基本单位是( C) 。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 2.设数据结构 A=(D,R),其中 D={1,2,3,4},R={r},r={<1,2>,<2,3>, <3,4>,<4,1>},则数据结构 A 是( C ) 。 (A) 线性结构 (B) 树型结构 (C) 图型结构 (D) 集合 3.数组的逻辑结构不同于下列(D )的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4.二叉树中第 i(i≥1)层上的结点数最多有( C)个。 (A) 2i (B) 2i (C) 2i-1 (D) 2i-1 5.设指针变量 p 指向单链表结点 A,则删除结点 A 的后继结点 B 需要的操作为 ( A ) 。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6.设栈 S 和队列 Q 的初始状态为空,元素 E1、E2、E3、E4、E5 和 E6 依次通过 栈 S,一个元素出栈后即进入队列 Q,若 6 个元素出列的顺序为 E2、E4、E3、E6、 E5 和 E1,则栈 S 的容量至少应该是( C ) 。 (A) 6 (B) 4 (C) 3 (D) 2 7.将 10 阶对称矩阵压缩存储到一维数组 A 中,则数组 A 的长度最少为( C ) 。 (A) 100 (B) 40 (C) 55 (D) 80 8.设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点,则结点 B 的度数数 为( B ) 。 (A) 3 (B) 4 (C) 5 (D) 1 9.根据二叉树的定义可知二叉树共有( B )种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10. 10. 设有以下四种排序方法,则( B )的空间复杂度最大。 (A) 冒泡排序 (B) 快速排序 (C) 堆排序 (D) 希尔排序 二、填空题(30 分) 1. 1. 设顺序循环队列 Q[0:m-1]的队头指针和队尾指针分别为 F 和 R, 其中队头指针 F 指向当前队头元素的前一个位置,队尾指针 R 指向当前队尾 元素所在的位置,则出队列的语句为 F =_(F+1) % m _;。 2. 2. 设线性表中有 n 个数据元素,则在顺序存储结构上实现顺序查找 的平均时间复杂度为_ O(n)_,在链式存储结构上实现顺序查找的平均时间 复杂度为_ O(n)_。 3. 3. 设一棵二叉树中有 n 个结点, 则当用二叉链表作为其存储结构时, 该二叉链表中共有__2n _个指针域,__ n+1___个空指针域。

22

4. 4.

设指针变量 p 指向单链表中结点 A,指针变量 s 指向被插入的结点 B,

5. 6. 7. 8.

则在结点 A 的后面插入结点 B 的操作序列为_ s->next=p->next; s->next=s _。 5. 设无向图 G 中有 n 个顶点和 e 条边,则其对应的邻接表中有__ n _个表头结点和__2e __个表结点。 6. 设无向图 G 中有 n 个顶点 e 条边,所有顶点的度数之和为 m,则 e 和 m 有_ m=2e __关系。 7. 设一棵二叉树的前序遍历序列和中序遍历序列均为 ABC,则该二 叉树的后序遍历序列为_ CBA _。 8. 设一棵完全二叉树中有 21 个结点,如果按照从上到下、从左到 右的顺序从 1 开始顺序编号,则编号为 8 的双亲结点的编号是___4___,编

号为 8 的左孩子结点的编号是___16___。 9. 9. 下列程序段的功能实现子串 t 在主串 s 中位置的算法,要求在下 划线处填上正确语句。 int { index(char s[ ], char t[ ]) i=j=0; while(i<strlen(s) && j<strlen(t)) if(s[i]==t[j]){i=i+l; j=j+l;} else{i= i-j+1__; j=_0_;} if (j==strlen(t))return(i-strlen(t));else return (-1); } 10. 10. 设一个连通图 G 中有 n 个顶点 e 条边,则其最小生成树上有_ n-1__ 条边。 三、应用题(30 分) 1.设完全二叉树的顺序存储结构中存储数据 ABCDE,要求给出该二叉树的链式 存储结构并给出该二叉树的前序、中序和后序遍历序列。 2.设给定一个权值集合 W=(3,5,7,9,11),要求根据给定的权值集合构造一 棵哈夫曼树并计算哈夫曼树的带权路径长度 WPL。 3. 设一组初始记录关键字序列为(19, 21, 16, 5, 18, 23), 要求给出以 19 为基准的一趟快速排序结果以及第 2 趟 直接选择排序后的结果。 4. 设一组初始记录关键字集合为(25, 10, 8, 27, 32, 68), 散列表的长度为 8,散列函数 H(k)=k mod 7,要求分别 用线性探测和链地址法作为解决冲突的方法设计哈希 表。 5.设无向图 G(所右图所示) ,要求给出该图的深度优先

23

和广度优先遍历的序列并给出该图的最小生成树。 四、算法设计题(20 分) 1. 1. 设计判断单链表中结点是否关于中心对称算法。 2. 2. 设计在链式存储结构上建立一棵二叉树的算法。 3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。 数据结构试卷参考答案 三、应用题 h1 ? ? 8 1. 1. h 2. 3. 4.
2

h0

链式存储结构略,前序 ABDEC,中序 DBEAC,后序 DEBCA。

2. 哈夫曼树略,WPL=78 h3 ? ? 10 0 1 2 , 3(5, 4 16, 5 216 7,18,23) 3. (18,5,16,19,21,23) ,19 h4 ? ? 25? ? 32 h5 ? ? 68 4. 线性探测: ? 8 ? 10 25 32 27 68 链 地 址
h6 ? ? 27





5. 5. 深度:125364,广度:123456,最小生成树 T 的边集为 E={(1, 4),(1,3),(3,5),(5,6),(5,6)} 四、算法设计题 1. 1. 设计判断单链表中结点是否关于中心对称算法。 typedef struct {int s[100]; int top;} sqstack; int lklistsymmetry(lklist *head) { sqstack stack; stack.top= -1; lklist *p; for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0); return(1); } 2. 2. 设计在链式存储结构上建立一棵二叉树的算法。 typedef char datatype; typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; void createbitree(bitree *&bt) { char ch; scanf("%c",&ch); if(ch=='#') {bt=0; return;}

24

bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); } 3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。 int minnum=-32768,flag=1; typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inorder(bt->rchild);} }

25


相关文章:
数据结构试题及答案(2).doc
数据结构试题及答案(2) - 数据结构试题 一、 单选题(每题 2 分,共 20
数据结构试卷及答案2套.doc
数据结构试卷及答案2套 - 数据结构试卷 1 一、单项选择题:(每小题 2 分,
数据结构复习题及答案 2.doc
数据结构复习题及答案 2 - 《数据结构》模拟试题一 一、单选题(每题 2 分,
数据结构试卷2(含答案).pdf
数据结构试卷2(含答案) - 数据结构期末试卷 出卷人:09 数煤(1)班 1~
数据结构试题及答案(免费).doc
数据结构试题及答案(免费) - 数据结构试卷(十一) 一、选择题(30 分) 1
数据结构试题和答案2.doc
数据结构试题和答案2 - 限锤雷锌娠垫步吼 弹自乐骨媳醋 世榆缺涅乏写 戳沏择昏
数据结构试题2(含答案).doc
数据结构试题2(含答案) - 期末样卷参考答案 一.是非题(每题 2 分共 20
数据结构联考试卷2及答案.pdf
数据结构联考试卷2及答案 - 试卷 2 一、单项选择题 (每小题 2 分,共 30 分) 1. 在数据结构中,数据的逻辑结构可以分成( A. 动态结构和静态结构 C. 线性...
数据结构试题及答案修2资料.doc
数据结构试题及答案修2资料 - 试卷一 一、 单选题(每题 2 分,共 20 分) 1. 对一个算法的评价,不包括如下()方面的内容。 A.健壮性和可读性 2. B....
数据结构试卷及参考答案_2.doc
数据结构试卷及参考答案_2_工学_高等教育_教育专区。数据结构试卷(二)一、选择
数据结构期末试题及答案 2.doc
数据结构期末试题及答案 2 - D 一、单项选择题 1、在以下的叙述中,正确的是
数据结构 试题(A)-答案 (2).doc
数据结构 试题(A)-答案 (2) - 第二学期“数据结构”考试试题(A) 姓名
数据结构试卷(二)及答案.doc
数据结构试卷(二)及答案 - 数据结构试卷( 数据结构试卷(二) 一、选择题(2
数据结构考试试题及答案.doc
数据结构考试试题及答案 - 数据结构考试试题及答案 【篇一:数据结构试题及答案】 数据结构试卷(二)... 5 数据结构试卷(三)......
中南大学十套数据结构试题及答案2.doc
中南大学十套数据结构试题及答案2_计算机软件及应用_IT/计算机_专业资料。数据
计算机应用基础数据结构部分试题及答案 (2).doc
计算机应用基础数据结构部分试题及答案 (2)_IT认证_资格考试/认证_教育专区。计算机应用基础数据结构部分试题及答案 (2) 计算机应用基础数据结构部分试题及答案(...
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 二、填空题(每空 1 分,共 2
2016数据结构试卷B及答案 (2) - 副本 - 副本.doc
2016数据结构试卷B及答案 (2) - 副本 - 副本 - ( 密封线内不答题
十套数据结构试题及答案.doc
十套数据结构试题及答案 - 数据结构试卷(一) 二、填空题(每空 1 分,共 2
2012数据结构试卷A及答案 - 副本 (2)_图文.doc
2012数据结构试卷A及答案 - 副本 (2) - ( 密封线内不答题 ) ……