数据结构07082试卷A

122-《数据结构》试卷A参考答案
烟台大学成人高等教育期末考试《数据结构与算法》试卷A 参考答案及评分标准
一、
1．算法的特征：有穷性、确定性、可行性、有输入、有输出。

算法设计的要求：正确、可使用、可读、健壮、高效。

2．数据元素之间的逻辑结构：集合、线形、树形、图形结构
逻辑结构的本质性：数据结构在用户面前的呈现形式，数据元素之间的邻接关系的描
述，与数据的存储无关，独立于计算机。

3．抽象数据类型：
数据元素描述
数据之间的逻辑关系描述
施加在数据上的基本操作
4．（1）链式存储；插入、删除操作频繁，适合链式存储的特点。

（2）顺序存储：数据移用少，随机存储，适合顺存储特点
5. （1）需要求解的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法
与原问题相同，只是规模减小。

（2）递归调用的次数是有限的。

（3）必须有结束递归的条件。

二、
1．n-i+1
2. a b c a b c a a a
-1 0 0 0 1 2 3 4 1
3. GetHead((a,b,c))=(a,b,c)
GetHead(GetTail((a,b),(c,d )))=(c,d)
4. 15
5. 图。

__________________学院__________级___________班 姓名_______________ 学号_______________………………………………（密）………………………………（封）………………………………（线）………………………………密 封 线 内 答 题 无 效2007－2008学年度第二学期期末考试数据结构试卷 B 卷答卷说明：1.本试卷共9页，五个大题，满分100分，120分钟完卷。

2.本试卷为闭卷考试，请将所有题目直接做在试卷上。

一、单项选择题(每题21．单循环链表的尾结点的指针域的值为( )。

A) NULL B) 0 C) 首结点地址 D) 尾结点地址2．设有一个足够大的栈，入栈元素的顺序为wxyz,，则栈的可能输出序列是（ ）。

A ）zwyx B ）ywxz C ）wxyz D ）zxyw3．设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x 和y 串的连接串，subs(s, i, j)返回串s 的从序号i 开始的j 个字符组成的子串，len(s)返回串s 的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是： Ａ) BCDEF Ｂ) BCDEFG Ｃ) BCPQRST Ｄ) BCDEFEF4．若广义表A=（(a,b,c),(d,e,f )）,则式子GetHead(GetTail(GetHead(GetTail(A))))的值为（）。

A ）（a,b,c ）B ）(d,e)C ）eD ）f5．下列程序段的时间复杂度是（）。

i=1;while (i<=n) i*=2;A）O(1) B）O(㏒2n) C）O(n) D）O(n2)6．已知一算术表达式的中缀形式为A＋B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。

A）–A+B*C/DE B）–A+B*CD/EC）–+*ABC/DE D）–+A*BC/DE7．假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（）。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。

数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。

答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。

答案：队尾、队头11. 二叉树中的节点包括______和______。

答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。

答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。

专升本)数据结构A卷参考答案:简答题1,数据结构是相互之间存在一种或多种特定关系的数据元素的集合.这种数据元素相互之间的关系称为结构.可以将数据结构形式化地定义为二元组:Data_Structure=(D,S)其中:D是数据元素的有限集,S是D上关系的有限集.数据结构课程主要讨论数据的逻辑结构,物理结构和操作三个方面的问题.2,算法的时间复杂度是指算法中各语句的频度之和T(n),其中频度指语句的执行次数,n指问题的规模,一般为数据的输入量.渐近时间复杂度:当问题的规模n趋于无穷大时,T(n)的数量级(阶).记为T(n)=O( f(n) ).这里"O"是一种近似表示法,其含义是:在n较大时,该算法的运行时间和f(n)成正比,或者说,T(n)的数量级和f(n)的数量级相同.实际中,将渐近时间复杂度简称为时间复杂度,用以描述算法的时间特性.3,顺序表的优点:(1)可直接求出存储地址(随机存储结构),结构简单,便于随机访问表中的任一元素.(2)存储密度高.顺序表的缺点:(1)不便于插入和删除.(移动元素次数多,平均约需移动一半元素)(2)不便于扩充表的容量.(3)不能有效地利用内存空间.单链表的优点:(1)结点空间可动态申请动态释放.(2)每个结点有指针域指示逻辑顺序,进行插入删除操作时不需移动元素.单链表的缺点:(1)不能随机访问表中任一元素,效率低.(2)存储量可随意扩充,但新增加的存储空间可能与以前的不邻接,故需要设立一些存放地址用的存储单元.4,入栈算法:int push (qstype *s, elemtype x){if (s→top==MAXNUM-1)return 0;else { s→top++;s→stack [s→top]=x;return 1; }}出栈算法:elemtype pop(qstype *s){if (s→topnext!=NULL)if (p->data!=p->next->data)p=p->next;else{ q=p->next;p->next=q->next;free(q);}}return head;}2,#define m 100typedef struct btreenode{ elemtype data;struct btreenode *left;struct btreenode *right;} btree; /*二叉链表的形式化定义*/ void postorder(btree * b){btree * stack[m],*p;int tag[m],top=0;p=b;do{while (p!=NULL){ top++;stack[top]=p;tag[top]=0;p=p->left;}if (top>0){ p=stack[top];if (tag[top]==1){ top--;printf("%d",p->data);}if (top>0){ p=p->right;tag[top]=1;}}}while (p!=NULL&&top!=0)}。

淮阴工学院07 - 08 学年第 2 学期数据结构试卷A( 闭卷)题号一二三四五六七八九总分得分一、选择题（本大题共15小题，每题2分，共30分；答案填在下表内）1 2 3 4 5 6 7 8 9 10 11 12 13 14 151.从一个长度为100的顺序表中删除第30个元素时需向前移动 A 个元素A、70B、71C、69D、302.在一个具有N个单元的顺序表中,假定以地址低端(即下标为1的单元)作为底,以top作为顶指针,则当做进栈处理时top变化为_D_。

A、 top不变B、top=0C、top=top-1D、top=top+13.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功情况下,则平均比较_D___个结点。

A、nB、n/2C、(n-1)/2D、(n+1)/24.在一个单链表中,若要删除p指针所指结点的后继结点,则执行BA、p-> next; p-> next=p-> next-> next;B、p-> next=p-> next-> next;C、p=p-> next;D、p=p-> next->>next;5.在一个链队列中,假定front和rear分别为队首和队后指针,则进行插入S结点的操作时应执行C _。

A、front-> next=s； front=s；B、s-> next=rear; rear=s；C、rear-> next=s; rear=s；D、s-> next=front; front=s；6.在一棵度为3的树中度为3的结点数为3个,度为2的结点数为1个,度为1的结点数为1个,那么度为0的结点数为_C_个A、6B、7C、 8=3+2+1+1D、97.假定一棵二叉树的结点数为33个,则它的最小高度为_C_,最大高度为_C__A、 4,33B、5,33C、6,33D、6,328. 在一棵完全二叉树中,若编号为i的结点有右孩子,则该结点的右孩子编号为_B__。

2008级数据结构试卷A及答案(A) Improve the basic operations. (B) Minimize the number of disk accesses.(C) Eliminate the recursive calls. (D) Reduce main memory use.(7) The max-heap constructed by a sequence of key (54, 32, 45, 63, 76, 84) is( D )?(A) 84, 63, 54, 76, 32, 45 (B) 84, 76, 45, 63, 54, 32(C) 84, 63, 76, 32, 45, 54 (D) 84, 76, 54, 63, 32, 45(8) If there is 1MB working memory, 8KB blocks, yield 128 blocks for working memory. By the multi-way merge in external sorting, the average run size and the sorted size in one pass of multi-way merge on average are separately ( C )?(A) 1MB, 128 MB (B) 2MB, 512MB(C) 2MB, 256 MB (D) 1MB, 256MB(9) Tree indexing methods are meant to overcome what deficiency in hashing?( D )(A) Inability to handle range queries. (B) Inability to maximum queries(C) Inability to handle queries in key order (D) All of above.(10) Assume that we have eight records, with key values A to H, and that they are initially placed in alphabetical order. Now, consider the result of applying the following access pattern: F D F G E G F A D F G E, if the list is organized by the move-to-front heuristic, then the final list will be ( B ).(A)E G F D A C H B (B) E G F D A B C H(C) F D G A E C B H (D) F D G E A B C H2. Fill the blank with correct C++ codes: (15 scores)(1)Given an array storing integers ordered by value, modify the binary searchroutines to return the position of the first integer with the greatest value less than K when K itself does not appear in the array. Return ERROR if the least value in the array is greater than K: (12 scores)// Return position of greatest element <= Kint newbinary(int array[], int n, int K) {int l = -1;int r = n; // l and r beyond array boundswhile (l+1 != r) { // Stop when l and r meet___ int i=（l+r）/2_____; // Look at middle of subarrayif (K < array[i]) __ r=i ___; // In left halfif (K == array[i]) __ return i ___; // Found itif (K > array[i]) ___ l=i ___ // In right half}// K is not in array or the greatest value is less than Kif K> array[0] （or l !=-1）then return l ; // the first integer with the greatest value less than// K when K itself does not appear in the array else return ERROR; // the least value in the array is greater than K}(2) A full 6-ary tree with 100 internal vertices has ___601___vertices. ( 3 scores)3. A certain binary tree has the preorder enumeration as ABECDFGHIJ and the inorder enumeration as EBCDAFHIGJ. Try to draw the binary tree and give the postorder enumeration. (The process of your solution is required) (8 scores)Postorder enumeration : EDCBIHJGFA4. Determine Θ for the following code fragments in the average case. Assume that all variables are of type int.(6 scores)(1) sum=0;for (i=0; i<3; i++)for (j=0; jsum++; solution : Θ___(n)_______(2) sum = 0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)sum++; solution : Θ__(n 2)________(3) sum=0;if (EVEN(n))for (i=0; isum++;elsesum=sum+n; solution : Θ___(n)_____5. Trace by hand the execution of Quicksort algorithm on the array:int a[] = {265 301 751 129 937 863 742 694 76 438} The pivot is 265 in the first pass, the second is 76 and 751, the third is 438 and 863, the four is 694, and so on till the algorithm is finished. (9 scores)initial: 265 301 751 129 937 863 742 694 76 438pass 1: [76 129] 265 [751 937 863 742 694 301 438]pass 2: 76 [129] 265 [438 301 694 742] 751 [863 937]pass 3: 76 129 265 [301] 438 [694 742] 751 863 [937]pass 4: 76 129 265 301 438 694 [742] 751 863 937pass 5: 76 129 265 301 438 694 742 751 863 937final sorted array:76 129 265 301 438 694 742 751 863 9376. Build the Huffman coding tree and determine the codes for the following set of letters and weights:A B C D E F G H5 25 36 10 11 36 4Draw the Huffman coding tree and give the Huffman code for each letters. What is the expected length in bits of a message containing n characters for this frequency distribution? (The process of your solution is required) (9 scores)Total length: 4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257Expected length: 257/100=2.577. Assume a disk drive is configured as follows. The total storage is approximately 675M divided among 15 surfaces. Each surface has 612 tracks; there are 144 sectors/track, 512 byte/sector, and 16 sectors/cluster. The interleaving factor is five. The disk turns at 7200rmp (8.33 ms/r). The track-to-track seek time is 20 ms, and the average seek time is 80 ms. Now how long does it take to read all of the data in a 320 KB file on the disk? Assume that the file ’s clusters are spread randomly across the disk. A seek must be performed each time the I/O reader moves to a new track. Show your calculations. (The process of your solution is required) (8 scores)Answer ：The first question is how many clusters the file requires?DA cluster holds 16*0.5K = 8K. Thus, the file requires 320/8=40 clusters.The time to read a cluster is seek time to thecluster+ latency time + (interleaf factor ×rotation time).Average seek time is defined to be 80 ms. Latency time is 0.5 *8.33 ms(60/7200≈8.33ms),and cluster rotation time is 5 * (16/144)*8.33.Seek time for the total file read time is40* (80 + 0.5 *8.33+ 5 * (16/144)*8.33 ) ≈3551.85 ms Or 3551.51 when (60/7200≈8.3ms)8. Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of eleven slots (the slots are numbered 0 through 10). The hash functions to be used are H1 and H2, defined below. You should show the hash table after all eight keys have been inserted. Be sure to indicate how you are using H1 and H2 to do the hashing. ( The process of your solution is required)H1(k) = 3k mod 11 H2(k) = 7k mod 10+1Keys: 22, 41, 53, 46, 30, 13, 1, 67. (8 scores)Answer:H1(22)=0, H1(41)=2, H1(53)=5, H1(46)=6, no conflictWhen H1(30)=2, H2(30)=1 （2+1*1）%11=3，so 30 enters the 3rd slot;H1(13)=6, H2(13)=2 (6+1*2)%11=8, so 13 enters the 8th slot;H1(1)=3, H2(1)=8 (3+5*8)%11= 10 so 1 enters 10 (pass by 0, 8, 5, 2 );H1(67)=3, H2(67)=10 (3+2*10)%11= 1 so 67 enters 1(pass by 2)9. You are given a series of records whose keys are integers. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R. Show the 2-3 tree that results from inserting these records. （the process of your solution is required）(7 scores)MSBD P UA C GI N R T W10.1) Use Dijkstra’s Algorithm to find the shortest paths from C to all other vertices.(4 scores)2) Use Kruskal’s algorithm to find the minimum-cost spanning tree. (3 scores)3) Show the DFS tree for the following graph, starting at Vertex A. (3 scores)1)C to A: 4 (C,A); CF: 5(C,F); CD: 6(C,A,D); CB: 12(C,A,D,B); CG:11 (C,F,G); CE: 13(C,A,D,B,E)2)OR3)A---->B---->D--->F---->C GE。

数据结构考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么类型的数据结构来实现？A. 栈B. 队列C. 数组D. 链表答案：C2. 下列选项中，哪一个不是二叉树的性质？A. 任意节点的左子树和右子树的深度可能不同B. 任意节点的左子树和右子树的深度相同C. 任意节点的左子树和右子树的节点数可能不同D. 任意节点的左子树和右子树的节点数相同答案：B3. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D4. 以下哪种排序算法的时间复杂度最低？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B5. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：B6. 以下哪种数据结构可以有效地实现稀疏矩阵的存储？A. 顺序存储B. 链表C. 散列D. 邻接矩阵答案：C7. 在二叉搜索树中，插入一个新节点后，树的平衡因子可能为：A. -2B. 0C. 2D. 3答案：A8. 堆数据结构中，父节点的值总是大于其子节点的值，这种堆被称为：A. 最小堆B. 最大堆C. 完全二叉树D. 满二叉树答案：B9. 以下哪个算法不是动态查找表的算法？A. 直接查找B. 二分查找C. 斐波那契查找D. 哈希查找答案：A10. 在图的遍历算法中，广度优先搜索（BFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种______结构，遵循后进先出（LIFO）的原则。

答案：线性2. 一个具有n个顶点的无向图的边数最多为______。

答案：n*(n-1)/23. 快速排序算法的时间复杂度在最坏情况下为______。

答案：O(n^2)4. 在哈希表中，如果一个关键字的哈希地址已经被占用，则需要进行______。

数据结构考试试题及答案### 数据结构考试试题及答案#### 一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构被称为什么？ - A. 栈- B. 队列- C. 数组- D. 链表答案：C2. 以下哪个是二叉树的遍历算法？- A. 深度优先搜索- B. 广度优先搜索- C. 选择排序- D. 插入排序答案：A3. 哈希表解决冲突最常用的方法是？- A. 链地址法- B. 开放地址法- C. 再散列法- D. 所有选项都是答案：A4. 堆数据结构通常用于实现哪种数据结构？- A. 栈- B. 队列- C. 优先队列- D. 链表答案：C5. 以下哪个排序算法是稳定的？- A. 快速排序- B. 归并排序- C. 堆排序- D. 选择排序答案：B#### 二、简答题（每题10分，共20分）1. 简述什么是递归，并给出递归函数的基本形式。

答案：递归是一种在函数中调用自身的编程技术。

递归函数通常包含两个部分：基本情况（base case）和递归步骤（recursive case）。

基本情况用于终止递归调用，而递归步骤则是函数调用自身以逐步接近基本情况。

2. 解释什么是图的深度优先搜索（DFS）算法，并说明其基本步骤。

答案：深度优先搜索（DFS）是一种遍历图的算法，它从一个顶点开始，尽可能深地搜索图的分支。

基本步骤包括：- 从源顶点开始，标记为已访问。

- 访问所有未访问的邻接顶点。

- 对每个邻接顶点递归执行DFS。

- 回溯到上一个顶点，继续搜索。

#### 三、算法题（每题15分，共30分）1. 给定一个数组，请编写一个函数来实现冒泡排序算法。

答案：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arr```2. 编写一个函数，实现二叉树的前序遍历。