河南工业大学数据结构2012级试卷A

2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为C。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．数据结构在计算机内存中的表示是指A。

A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的A结构。

A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑A。

A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是D。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是C，算法分析的两个主要方面是A。

（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O（n2）。

s ＝0；for（I ＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝s ；9．下面程序段的时间复杂度是O（n*m）。

for（i ＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝0；10．下面程序段的时间复杂度是O（log3n）。

i ＝0；while（i＜＝n）i ＝i * 3；11．在以下的叙述中，正确的是B。

A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。

得 分 评分人贵州大学2011-2012学年第二学期考试试卷 A数据结构注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

题 号一二三四总 分统分人得 分一、单项选择题（共20分,每小题2分）1．不是四类基本逻辑结构之一的是 （ ）A 、集合 B 、链表结构C 、树形结构 D 、网状结构2．关于队列的描述，错误的是 （ ）A 、队列的头指针指下一个入队的位置B 、普通队列要求满足“先进先出”C 、使用一个队列可以模拟一个银行的多个同性质服务窗口的排队状况D 、循环队列可以采用顺序表实现3．在n 个结点的顺序表中，算法的时间复杂度是O （1）的操作是（ ）A 、访问第i 个结点（1≤i≤n ）和求第i 个结点的直接前驱（2≤i≤n ）B 、在第i 个结点后插入一个新结点（1≤i≤n ）C 、删除第i 个结点（1≤i≤n ）D 、将n 个结点从小到大排序4．下列关于串的叙述中，正确的是 （ ）A 、一个串的字符个数即该串的长度B 、一个串的长度至少是1C 、空串是由一个空格字符组成的串得 分评分人D 、两个串S1和S2若长度相同，则这两个串相等5．稀疏矩阵一般的压缩存储方法有两种，即 （）A 、二维数组和三维数组B 、三元组和散列C 、三元组和十字链表D 、散列和十字链表6．按照二叉树的定义,具有3个结点的二叉树有 （）A 、3种B 、4种C 、5种 B 、6种7．不是图的存储结构的是 （ ）A 、邻接多重表B 、十字链表C 、关联矩阵D 、可利用空间表 8．在关于动态存储管理，错误的说法是 （ ）A 、未被占用的连续地址空间称为空闲块B 、可利用空间表一般采用链表C 、针对内存申请块的大小范围较广时，应该采用首次拟合法D 、针对内存申请块的大小较均匀时，应该采用最差拟合法9．理想情况下，速度最快的查找结构的是 （ ）A 、分块索引B 、二叉排序树C 、二叉平衡树D 、哈希表10. 关于各种排序方法，错误的说法是 （ ）A 、关键字大小相同的记录，排序后先后顺序不改变，则称为此排序为稳定的B 、内部排序算法的性能由关键字比较次数和记录移动次数决定C 、冒泡排序的时间复杂度为O(nlogn)D 、堆排序使用的堆对应一棵完全二叉树二、概念填空题（共20分,每空2分）1．若使用伙伴系统进行动态存储管理，若申请32个字，选中的空闲块有128个字，则这个空闲块会被分裂为__________个块（最小块大小可以为4）。

南阳理工学院 2013 – 2014 学年第 一 学期试卷（A 卷）课程：《数据结构》课程号：1504108130、考核方式：（闭卷） 课程性质： 专业必修课 适用对象： 11级软件工程本科（）11 级 软件工程 本科一、填空题：（每空 2 分，共 20 分）1．带有头结点的单链表L 的判空条件为_____________________。

2．在一个具有n 个单元的顺序栈中，假设以地址高端作为栈底，以top 作为栈顶指针，则当作进栈处理时，top 的变化为_____________________。

3．最大容量为n 的循环队列Q ，队尾指针是rear ，队头是front ，则队空的条件是______________________________。

4．假设以行序为主序存储二维数组A=array[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]= _______________。

5．由3 个结点可以构造出_________种不同的二叉树。

6．一个具有1025个结点的完全二叉树的高h 为__________。

7．具有n 个顶点的有向完全图有________________条边。

8．n 个顶点的连通图用邻接矩阵表示时，该矩阵至少有___________个非零元素。

9．对n 个不同的排序码进行冒泡排序，在最坏的情况下比较的次数最多为___________。

10．快速排序的平均时间复杂度为______________。

二、选择题：（每题 2 分，共 20 分）1．以下与数据的存储结构无关的术语是（ ）。

A ．有序表B. 链表C.顺序队列D. 链栈 2．链接存储的存储结构所占存储空间（ ）。

A ．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B ．只有一部分，存放结点值C ．只有一部分，存储表示结点间关系的指针D ．分两部分，一部分存放结点值，另一部分存放结点所占单元数3．在一个长度为n 的顺序表中，在第i 个元素（1≤i ≤n+1）之前插入一个新元素时须向后移动（ ）个元素。

学院名称 专业班级： 姓名： 学号： 我密 封 线 内 不 要 答 题┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ 密┃┃┃┃┃┃┃┃┃┃┃ 封┃┃┃┃┃┃┃┃┃┃┃ 线┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃2012 至 2013 学年第 2 学期数据结构与算法试卷A 卷出卷教师： 适应班级：空信1201－1202 考试方式：闭卷 本试卷考试分数占学生总评成绩的 80 %题号 一 二 三 四 总分 核分人得分复查总分 总复查人一、选择题（本题15分,每小题1分）请将正确的答案填入下面的表格中：1 2 3 4 5 6 7 8 9 10 11 12 13 14 151. 算法分析的目的是 。

A 、找出数据结构的合理性B 、研究算法中的输入和输出关系C 、分析算法的效率以求改进D 、分析算法的易懂性和文档性2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ ____。

A 、必须是连续的B 、部分地址必须是连续的C 、一定是不连续的D 、连续或不连续都可以3. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_________。

A 、O(1)B 、O(n)C 、O(n 2)D 、O(nlog 2n) 4. 栈的插入和删除操作在___ ___进行。

A 、栈顶B 、栈底C 、任意位置D 、指定位置 5. 稀疏矩阵一般的压缩存储方法有两种，即____ ___。

A 、二维数组和三维数组 B 、三元组和散列C 、三元组和十字链表D 、散列和十字链表6. 依次在初始为空的队列中插入元素为a,b,c,d 以后，紧接着作了两次删除操作，此时的队头元素是（ ）A. aB. bC. cD. d 7. 广义表（（a ））的表尾是____ ___。

A 、a B 、（a ） C 、（ ） D 、（（a ）） 8. 下面4棵二叉树，是平衡二叉树的是____ ___。

A B C D 9. 求字符串T 在字符串S 中首次出现的位置的操作称为 （ ） A. 串的模式匹配 B. 求子串 C. 求串的长度 D. 串的连接 10. 深度为5的二叉树至多有____ ___个结点。

信息学院考试试卷及参考答案Array 2012学年第一学期课程名称：数据结构一、填空殖(每空1分共20分)1.数据的物理结构主要包括_____________和______________两种情况。

2.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

3.设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。

4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。

5.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。

6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。

7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。

8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。

9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。

10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。

11.设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。

12.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。

2012数据结构试卷A及答案-副本（2）stored at 676(10), and every element occupies one space. “(10)” means that the number is presented in decimals. Then the element A[3][3](10) is at position:( B )(A) 692 (B) 668 (C) 650 (D) 708(9) Which statement is not correct among the following four: ( A)(A)The number of empty sub-trees in a non-empty binary tree is one less than thenumber of nodes in the tree.(B)The Mergesort is a stable sorting algorithm.(C)The root of a binary tree transferred from a general tree has only left child.(D)A sector is the smallest unit of allocation for a record, so all records occupy amultiple of the sector size.(10) Assume that we have eight records, with key values A to H, and that they are initially placedin alphabetical order. Now, consider the result of applying the following access pattern: F D FG E G F A D F G E if the list is organized by the transpose heuristic, then the final list will be( B ).(A)A F C D H G E B (B) A B F D G E C H(C) A B F G D C E H (D) A H F D G E C B2. Fill the blank with correct C++ codes: (18 scores)(1)Given an array storing integers ordered by value, modify the binary searchroutines to return the position of the first integer with the least value greater than K when K itself does not appear in thearray. Return ERROR if the greatest value in the array is less than K: (14 scores)// Return position of lest 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_____; // Check middle of remaining 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[n-1] or r!=nthen return r; // the first integer with the least value greater than K// when K itself does not appear in the arrayelse return ERROR;// the greatest value in the array is less than K}(2)The height of the shortest tree and the tallest tree with both n nodes is respectively _2_or n(n<2) and __n_ , suppose that the height of the one-node tree is 1 ( 4 scores)3. Please calculate the number of binary trees in different shape with 5 nodes in total, and 6 nodes? (4 scores) 5:42, 6:132,C 2n n /n+14. A certain binary tree has the preorder enumeration as ABCDFEGIHJ and the inorder enumeration as BCDAEFGHIJ. Try todraw the binary tree and give the postorder enumeration. (The process of your solution is required) (6 scores)Postorder enumeration : DCBEHJIGFA5. Trace by hand the execution of Radix-sort algorithm on the array : int a[] = {265 301 751 129 937 863 742 694 076 438}.(6 scores)initial: 265 301 751 129 937 863 742 694 076 438pass 1: [] [301 751] [742] [863] [694] [265] [076] [937] [438] [129] pass 2: [301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694] pass 3: [075] [129] [265] [301] [438] [] [694] [742 751] [863] [937] final sorted array: 075 129 265 301 438 694 742 751 8639376. (a) Describe simply the main tasks of the two phases of external sorting. (4 scores)The task of first phase is to break the files into large initial runs by replacement selection; the second phase is to merge the runs together to form a single sorted run file.(b)Assume that working memory is 256KB broken into blocks of 8192 bytes (there is also additional space available for I/O buffers, program variables, etc.) What is the expected size for the largest file that can be merged using replacement selection followed by two passes of multi-way merge? Explain how you got your answer. (4 scores)Since working memory is 256KB and the blocksize is8KB,the working memory holds 32 blocks. The expected runlength is 512KB, so a single pass of multiway merge forms runs of length 512KB*32=16MB. The second pass then forms a run as large as 16MB*32=512MB.7. Assume a disk drive is configured as follows. The total storage is approximately675M 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 3. Thedisk turns at 7200rmp (8.3ms/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 360 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) (8cores)A cluster holds 16*0.5K = 8K. Thus, the file requires360/8=45clusters.The time to read a cluster is seek time to the cluster+ latency time + (interleaf factor × rotation time).Average seek time is defined to be 80 ms. Latency time is 0.5 *8.3, and cluster rotation time is 3 * (16/144)*8.3.Seek time for the total file read time is 45* (80 + 0.5 * 8.3+ 3 * (16/144)*8.3 ) = 3911.258. 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 areusing H1 and H2 to do the hashing. ( The process of your solution is required) H1(k) = 3k mod 11 H2(k) = 7k mod 10+1 Keys: 22, 31, 19, 35, 41, 13, 1, 67. (8 scores)Answer:H 1(22)=0, H 1(31)=5, H 1(19)=2, H 1(35)=6, no conflictWhen H 1(41)=2, H 2(41)=8 （2+8*1）%11=10，so 41 enters the 10rd slot; H 1(13)=6, H 2(13)=2 (6+1*2)%11=8, so 13 enters the 8th slot; H 1(1)=3, so 1 enters 3 ;H 1(67)=3, H 2(67)=10 (3+2*10)%11= 1 so 67 enters 1(pass by 2)9.. Converting from a general tree to a binary tree. (4 scores)10.Figure 1 Example graph(a) Draw the adjacency matrix representation and adjacency list representation forthe graph of the figure-1. (6)(b) Use Dijkstra’s Algorithm to find the shortest paths from Vertex1 to all the other vertices. (6)(c) Use Kruskal’s algorithm to find the minimum-cost spanning tree. (4)(a) adjacency matrix1 2 3 4 5 6--------------------------1 | 10 202 |2 | 103 5 |3 | 3 15 |4 | 205 11 10 |5 | 15 11 3 |6 | 2 10 3 |--------------------------adjacency list:1 -> 2(10) -> 4(20) -> 6(2) -> \2 -> 1(10) -> 3(3) -> 4(5) -> \3 -> 2(3) -> 5(15) -> \4 -> 1(20) -> 2(5) -> 5(11) -> 6(10) -> \5 -> 3(15) -> 4(11) -> 6(3) -> \6 -> 1(2) -> 4(10) -> 5(3) -> \(b) 1 to 2: 10 (1,2);1 to 3: 13(1,2,3);1 to 4: 12 (1,6,4);1 to 5: 5 (1,6,5);1 to 6:2 (1,6,);(c)。

河南师范大学软件学院2013――2014学年度第一学期2012年级期末考试《数据结构》A 卷1．在n 个结点的顺序表中，算法的时间复杂度是O （1）的操作是：（ ） A ．访问第i 个结点（1≤i ≤n ）和求第i 个结点的直接前驱（2≤i ≤n ） B ．在第i 个结点后插入一个新结点（1≤i ≤n ） C ．删除第i 个结点（1≤i ≤n ） D ．将n 个结点从小到大排序2．线性表L 在（ ）情况下适合选用链式结构实现。

A ．L 中含有大量的结点 B ．需要经常修改L 中结点值 C ．需不断对L 进行插入删除操作 D ．L 中结点结构复杂3．一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ） A ．1，3，2，4 B ．2，3，4，1 C ．4，3，1，2 D ．3，4，2，1 4．下列叙述正确的是（ ）。

A ．二叉树是度为2的有序树B ．二叉树中结点只有一个孩子时无左右之分C ．二叉树中必有度为二的结点D ．二叉树中最多只有棵子树，并且有左右之分5．设有一个10阶的对称矩阵A ，采用下三角压缩存储方式，以行序为主序存储，a 11为第一元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。

A ．13 B ．33 C ．18 D ．406．设循环队列中数组的下标范围是1-n ，其头尾指针分别为f 和r ，则其元素个数为（ ）。

A ．r-f B ．r-f+1 C ．(r-f)mod (n+1) D ．(r-f+n) mod n7．在一个单链表中，已知q 所指结点是p 所指结点的前驱结点，若在q 和p 之间插入s 结点，则执行（ ）。

A ．s->next=p->next ；p->next=s ；B ．p->next=s->next ；s->next=p ；C ．q->next=s ；s->next=p ；D ．p->next=s ；s->next=q ；8．在串的块链存储结构中，通常将链串的结点大小设置为大于1是为了（ ）。

…………密…………封…………线…………内…………不…………要…………答…………题………………系 级 班 考生姓名 学号 任课教师姓名 第 选课教学班宜宾学院成人教育考试试卷(2011—2012学年第三学期） 课程名称：数据结构（Ａ卷）说明：1、本试题共 ？ 页 ？ 大题，适用于2011级 班 考试时间：90分钟 一. 选择题（每题2分，共60分）1、研究数据结构就是研究（ ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作 2、具有线性结构的数据结构是（ ）。

A. 图B. 树C. 广义表D. 栈 3、下面程序段的时间复杂度是（ ）。

for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j;A. O(m 2)B. O(n 2)C. O(m*n)D. O(m+n) 4、若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素算法的时间复杂度（ ）。

A. O(log 2n)B.O(1)C. O(n)D.O(n 2) 5、链表不具有的特点是（ ）。

A. 可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比6、在双向循环链表中，在p 指针所指的结点后插入一个指针q 所指向的新结点，修改指针的操作是（ ）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D. q->next=p->next;q->prior=p;p->next=q;p->next=q;7、在一个长度为n 的顺序表中删除第i 个元素，需要向前移动（ ）个元素。

C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s
7、有向图采用邻接矩阵存储，某一行中非零元素的个数等于
2、数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系
3、数据结构中，从逻辑上可以把数据结构分成(?)。
?A．动态结构和静态结构?B．紧凑结构和非紧凑结构?C．线性结构和非线性结构?D．内部结构和外部结构
1、若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是
A．top=top+1；V[top]=x B．V[top]=x；top=top+1
C．top=top一1；V[mp]=x D．V[top]=x；top=top—l
22、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
A LL B LR C RL D RR
23、若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用( )存储方法最节省时间
4、下述排序方法中，时间性能和待排序记录的初始状态无关的是（ ）
A 插入排序和快速排序 B 归并排序和快速排序
C 选择排序和归并排序 D 插入排序和归并排序
5、G是一个非连通无向图，共28条边，则 D 9

2022年河南工业大学数据科学与大数据技术专业《操作系统》科目期末试卷A（有答案）一、选择题1、在中断发生后，进入中断处理的程序属于（）。

A.用户程序B.可能是应用程序，也可能是操作系统程序C.操作系统程序D.既不是应用程序，也不是操作系统程序2、下列选项中，在用户态执行的是（）。

A.命令解释程序B.缺页处理程序C.进程调度程序D.时钟中断处理程序3、下列关于线程的叙述中，正确的是（）。

I.在采用轮转调度算法时，一进程拥有10个用户级线程，则在系统调度执行时间上占用10个时间片II.属于同·个进程的各个线程共享栈空间III.同一进程中的线程可以并发执行，但不同进程内的线程不可以并发执行IV.线程的切换，不会引起进程的切换A. 仅I、II、IIIB. 仅II、IVC.仅II、IIID.全错4、进程调度算法中，可以设计成可抢占式的算法有（）。

A.先来先服务调度算法B.最高响应比优先调度算法C.最短作业优先调度算法D.时间片轮转调度算法5、下列关于进程和线程的叙述中，正确的是（）A.不管系统是否支持线程，进程都是资源分配的基本单位，B.线程是资源分配的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都需要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间6、操作系统的I/O子系统通常由4个层次组成，每-层明确定义了与邻近层次的接口，其合理的层次组织排列顺序是（）。

A.用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序B.用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C.用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D.用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序7、下列关于设备驱动程序的叙述中，正确的是（）。

I.与设备相关的中断处理过程是由设备驱动程序完成的II.由于驱动程序与I/O设备（硬件）紧密相关，故必须全部用汇编语言书写III.磁盘的调度程序是在设备驱动程序中运行的IV.一个计算机系统配置了2台同类绘图机和3台同类打印机，为了正确驱动这些设备，系统应该提供5个设备驱动程序A. 仅I、IIIB. 仅II、IIIC.仅I、III，IVD. I、II、III、IV8、某文件系统中，针对每个文件，用户类别分为4类：安全管理员、文件上、文件主的伙伴、其他用户：访问权限分为5类：完全控制、执行、修改、读取、写入。

一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

A.表元素B.字符C.数据元素D.数据项(12) 线性表的存储结构是一种____ B ____的存储结构。

一、填空题（每空1 分，共10分）1．向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素。

2．带有一个头结点的单链表head为空的条件是head->next=head。

3．由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为44 。

4．设s=’I︺AM︺A︺TEACHER’，其长度是 14 。

5．二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是326。

6．假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数目个数为__ 1__。

7.深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点。

8．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于1。

9．执行广义表操作GetTail[ GetHead[ ((a,b),(c,d)) ] ]后的结果为（b）。

二、选择题（每小题1分，共10分）1.下列数据中，哪一个是非线性结构？( D )A. 栈B. 队列C. 字符串D. 二叉树2.设P指向单链表的某个节点，在P之后插入一个节点S的操作为( C)A. P->next = S;B. P->next = S->next; S->next = P->next;C. S->next = P->next; P->next = S;D. P->next = S; P = P->next;3．设三个元素的进栈顺序为abc，则下列哪个序列是不可能出现的出栈序列( D)A. abcB. acbC. cbaD. cab4 ．假设用块链存储结构表示串，如果每一个块的大小为4个字符（每个字符占用一个字节），一个指针占4个字节，则一个长为15的串需要多少字节的存储空间（C）A. 15B. 20C. 32D. 405．用一维数组存储一个6×6的对称阵A，以行序为主序存储该矩阵的下三角（包括对角线）元素，数组的起始位置为100，每个数组元素占4个字节，那么A[3][6]的存储位置为( A )A. 168B. 140C. 132D. 1086．设一个度为3的树中，度为1，2，3的结点个数分别为2，3，4，则该树中有多少个叶子结点？( D )A. 9B. 10C. 11D. 127．一个AOV网如图1所示，则下列哪一个序列不是该图的拓扑有序序列？( B)图1A. 124359786B. 123459786C. 142357896D. 4132578698．对一个长度为10的有序表进行折半查找，在等概率情况下查找成功的平均查找长度为( A)A. 2.9B. 3.0C. 3.2D. 3.49．下列排序算法中，那个算法是稳定的？( D)A. 希尔排序B. 快速排序C. 堆排序D. 归并排序10.设数据结构A = (D,R)。

得分
1. 设有一个单循环链表p如下图所示， ① 请画出执行p->next=p->next->next语句后的新链表
图; ② 若现有一个新结点q，如下图所示，则请在①基础上画出接着执行q>next=p->next; p->next=q; p=q; 语句序列后的新链表图。 p q data next z y x d
Hale Waihona Puke 得分1. 下列算法是输出邻接矩阵存储结构的有向图G各顶点的入度和出度， 请在空白处填入适当的语句，使该算法完整。 typedef int adjmatrix[MaxVertexNum] [MaxVertexNum]; void Graph( adjmatrix G, int n) { //G是n个顶点的邻接矩阵存储结构的有向图 int i, j, k, d; for(i = 0 ; i < n; i++) { d = 0; for(j=0; j < n; j++) if( ① ) d++; cout<<”顶点i的出度是”<<d<<”,”; d= ② ; for(k=0; k < n; k++)
if( ③ ) d++; cout<<”顶点i的入度是”<<d<<endl; } } 2. 一个双端队列是限定在两端end1和end2都可以进行插入和删除的 线性表。若用顺序方式来组织双端队列（构成一个循环队列），示意图 如下图所示，Q.end1指向一端的头元素的前一个位置，Q.end2指向 另一端的头元素位置，队列空条件为：Q.end1==Q.end2；队列满条 件为： (Q.end2+1)%MAXSIZE==Q.end1（此时有一个元素空间 为空）。初始状态时，Q.end1=Q.end2=0。入队列时，end1按照逆 时针方向进行，end2按照顺时针方向进行；出队列时方向相反。下列 算法是在指定端K（K为1或2）进行双端队列的插入操作，当k==1 时，在左端Q.end1操作；k==2时，在右端Q.end2操作，请在空白处 填入适当的语句，使该算法完整。 0 1 MAXSIZE-1 …. 8 5 6 …. end1 end2

数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。

武汉大学计算机学院2012年－2013学年第一学期“数据结构”考试试题（A ）姓名学号(序号)_ 班号要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共30分）1. 数据结构在计算机内存中的表示是指 。

A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系2. 若线性表最常用的运算是存取第i 个元素及其前趋元素的值，则采用 存储方式节省时间。

A.单链表B.双链表C.单循环链表D.顺序表3. 在一个具有n 个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为 。

A.O(log 2n)B.O(1)C.O(n 2)D.O(n) 4. 栈和队列的共同点是 。

A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有其同点5. 判定一个循环队列Q （存放元素位置为0～QueueSize-1，front 指向队中队首元素的前一个位置，rear 指向队中队尾元素的位置）队空的条件是 。

A.Q.front==Q.rearB.Q.front+1==Q.rearC.Q.front==(Q.rear+1)%QueueSizeD.Q.rear==(Q.front+1)%QueueSize 6. 串是 。

A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列 7. 一个n×n 的对称矩阵A ，如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B 中，则B 的容量为 。

A. n 2B.22nC. 2)1(+n nD.2)1(2+n8. 若一棵3次树中有a 个度为1的节点，b 个度为2的节点，c 个度为3的节点，则该树中有 个叶子节点。

A.1+2b +3cB.a +2b +3cC.2b +3cD.1+b +2c 9. 一棵完全二叉树中有501个叶子节点，则至少有 个节点。

二、综合应用题 41．解答：
2 1 1
图
1 2
A-5
3 1 4
图
1 1 2
A-6
2 3
该方法不一定能（或不能）求得最短路径。 （4 分） 举例说明： （6 分） 图 A-5 中，设初始顶点为 1，目标顶点为 4，欲求从顶点 1 到顶点 4 之间的最短路径， 显然这两点之间的最短路径长度为 2。利用给定方法求得的路径长度为 3，但这条路径并不 是这两点之间的最短路径。 图 A-6 中，设初始顶点为 1，目标顶点为 3，欲求从顶点 1 到顶点 3 之间的最短路径。 利用给定的方法，无法求出顶点 1 到顶点 3 的路径。 【评分说明】 ①若考生回答“能求得最短路径” ，无论给出何种证明，均不给分。 ②考生只要举出类似上述的一个反例说明“不能求得最短路径”或答案中体现了“局部
typedef int ElemType; typedef struct LNode{ ElemType data; struct Lnode *link; } *LinkList; int Search_k(LinkList list,int k){ //查找链表 list 倒数第 k 个结点，并输出该结点 data 域的值 LinkList p=list->link,q=list->link; //指针 p、q 指示第一个结点 int count=0; while(p!=NULL){ if(count<k) count++; else q=q->link;p=p->link; } //while if(count<k) return 0; else { printf(“%d”,q->data); return 1; } } //Search_k //查找失败返回 0 //否则打印并返回 1 //遍历链表直到最后一个结点 //计数，若 count<k 只移动 p //之后让 p、q 同步移动 //链表数据的类型定义 //链表结点的结构定义 //结点数据 //结点链接指针

2011 至 2012 学年第 二 学期计算机网络 试卷A 卷出卷教师： 适应班级：08信息01-06班考试方式： 闭卷 本试卷考试分数占学生总评成绩的 80 % 题号 一 二 三 四 五 六 七 八 九 十 总分 核分人 得分复查总分 总复查人一．单选题 (本大题共__30__题，每题__2__分，共__60___分。

)1、开放系统互连基本参考模型简称:( )A. ISOB. OSI/RMC. RMD. ISO RM 2、 源系统一般包括:( )A. 源点与终点B. 源点与发送器C. 接收器与终点D. 接收器与终点 3、 FTTH 被称为( )A. 光纤到路边B. 光纤到大楼C. 光纤到办公室D. 光纤到户 4、 载波的振幅随基带数字信号而变化的调制方法称为( ) A. 调频 B 调幅 C 调相 D 正交调制5、 由于码元波形时间变宽使接收端收到信号的波形失去码元之间的清晰界限的现象称为( )A 失真B 波形叠加C 码间串扰D 干扰 6、 信噪比S/N 与分贝(dB)之间的关系,以下描述正确的是( )A S/N 的单位是分贝B dB=log 10(S/N)C dB=10 log 10(S/N)D S/N= log 10(dB) 7、 以下关于PPP 协议描述正确的是( ) A. PPP 协议支持半双工和全双工 B. PPP 协议具有纠错功能C PPP 协议在使用SONET/SDH 链路时,是使用同步传输的.D 在同步传输情况下,PPP 协议采用零比特填充方法.8、 在CSMA/CD 协议中, 为解决碰撞检测问题,通常采用哪种方法?( ) A 载波侦听 B 多点检测 C 二进制指数退避 D 预约算法9、 与IP 协议配套使用的协议还有四个协议, 是哪四个?( ) A ARP RARP ICGP IGMP B ARP RAP IGMP OCMP C ARP RARP ICMP IGMPD TCP UDP ARP RARP10、 A 类地址的主机号占( )个字节.A 1B 2C 3D 411、在模拟传输中，为了实现找距离传输，每隔一定距离就要用（ ）来放大信号的强度以克服信号的衰减。