《数据结构》期末考A、B卷(本科)范文

厦门大学《＿数据结构＿》课程期末试卷信息科学与技术学院计算机科学系2009年级＿＿＿专业主考教师：陈怡疆庄朝晖试卷类型：（B卷）一、（本题10分）请根据下面的描述写出销售部门的数据结构（用C语言）：假设一个销售部门有n个职员（最多不超过N个，N为100），其中有一个是销售经理。

每个职员都各自有一些客户，客户的个数不固定，不同职员的客户不重叠。

答案：#define N 100typedef struct CustNode {Customer cust;struct CustNode * next;} CustNode, * CustLink;typedef struct {Saleman sm;CustLink firstcust; //指向第一个销售员} SalemanNode;typedef struct SaleDept {SalemanNode saleman[N];int n; //销售员的人数int manager; //销售经理在数组saleman[N]中的序号} SaleDept;二、（本题15分）（1）线性表和广义表的主要区别点是什么？已知广义表: C=(a,(b, (a,b)), ((a,b), (a,b))), 则tail(head(tail(C))) =？（2）满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？答：（1）线性表和广义表都是元素a1,a2,…,an组成的序列，其主要区别点在于：在线性表中，ai是单个元素（原子）；在广义表中，ai可以是单个元素（原子），也可以是广义表。

tail(head(tail(C))) = ((a,b))（2）序列a1,a2,…,an必须在数组（顺序表）中，且有序；时间复杂度为O(log n)。

三、（本题10分）给定一组权值（5，9，11，2，6，16），试设计相应的哈夫曼树。

解：构造的哈夫曼树如下图所示：四、（本题15分）某带权有向图如下：（3）将该图作为AOE 网络，写出求关键路径的过程。

数据结构期末试卷B3860A book, like a ship, leads us from a narrow place to an infinite sea of life, CalebData structure final paper B1, judge: 10 points, 1 point per question.A full binary tree is also a complete binary treeThe binary tree can be represented by an ordered tree of 0 or less than or equal to 2(a)In the k cross tree where there is only a degree of zero and a degree of k, there are nO of the nodes of 0, and nk for the nodes of k, and nO 二nk + 14,the shortest path to another vertex in a graph with the right connection is not necessarily the only oneIn the undirected graph of n nodes, if the number of edges is less than n minus 1, the graph must be an unconnected graph The binary tree with the shortest path length of the tree must have no node of 1The lookup of the hash table does not need to be compared to the keywordThe binary search method can be used to search for linear linked lists ordered by valueIterating over a heap does not necessarily get an ordered sequenceBecause the last trip of hill sort is the same as the direct insertion sort process, the former must spend more time than the latter2, fill in the blanks: (20 points, 2 points each.)A node with a degree of zero degrees is a node with no subtreesThe son of the same node is called a ____________In a binary linked list with n nodes, there is an empty chainThe adjacency matrix is used for the adjacency matrix storage method, and the adjacency matrix must be a4, a given sequence {100, 86, 4& 73, 35, 39, 42, 57, 66, 21}, as defined by the heap structure, it is an _____________________ heapIn the case of direct insertion sort, the number of data is compared with the initial order of data. In the case of direct selection, the number of data compared with the data is inThe function H, which converts the node keyword to the location of the node, is called __________________ or ____________The sequence of n key words is sorted rapidly, and the space complexity of the average case isChoice: 20 points, 2 points per problem・1, will be a totally has 100 node in the binary tree from top to bottom, from left to right in turn on node number, the serial number of the root node is 1, the number of node，s left child for 49 Numbers forA. 98 b. 99C. 50 d. 48The shape of the heap is aA. AC. complete binary tree d. balance binary treeFor the hash function H (key)二key MOD 13, the keyword that is called a synonym isA. 35 and 41 b. 23 and 39C. 15 and 44 d. 25 and 51Point out how many comparisons are required to find 12 in order tables {2, 5, 5, 7, 10, 14, 15, 1& 23, 35, 41, 52}A, 2, B, 3C, 4, D, 5Suppose a graph with an n vertex and an arc of e is indicatedby the adjacency list, and the time complexity associated with a vertex vi is removed: ___________________A. 0 (n) b. o. (e)C. 0 (n + e)D. 0 (n * e)When looking for dn element in a binary sort tree, its time complexity is approximatelyA, 0 (n) B, 0 (1)C, 0 (log2n) D, 0 (n2)The weight of a tree that has a weight of 3, 8, 6, 2, 5 leaves a Huffman tree with a right path length ofA, 24, B, 48C, 72, D, 53& A character sequence {Q, H, C, Y, P, A, M, S, D, F, R, X}, A trip to the sorting result for {F, H, C, D, P, A, M, Q, R,S, Y, X}, is which of the following sorting algorithmsA, blisters sort B, and the initial step is A sequence of 4 shellsC, 2 merge sort D, and the first element is the quicksort of the boundary elementA tree that is not connected to a connected graph is a.・・that contains all the vertices of the connected graphA: very little connected subgraph BC. greatly connected subgraphD. Large subgraphThe width of the diagram is first traversed by a type similar to the binary treeA. first order traversal B・ Sequence traversalThe post-order traversal of the DFour, answer the question: (total 28 minutes, each question 4)1,the binary tree that is shown in the picture is completed in order traversal, the following sequence traversal, the first sequence traversing, and drawing the binary tree of the middle sequence clues2,please give the adjacency matrix and the adjacency list below, and write the vertex sequence that is the highest priority and breadth of the graph from vertex aFor the diagram below, draw the minimum spanning treeA table 4, known as (49, 66, 73, 52, 40, 37, 65, 43), made according to the order of the elements in the table, in turn, insert a initial empty binary sort tree, draw the binary sort tree elements in the tableA three-order b~tree is shown below, assuming that the key words are removed in sequence, 46, 24, 815, and you can draw the tree after each delete node:6,known as a group of keywords, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79 (19), then the hash function H (key)二key MOD and linear detection method of conflict resolution structure of this group of 13 key hash tableDo you know if the following sequence is a heap? If not, adjust it to heap:(5, 56, 20, 234, 38,29,61,35, 76,28, 100)Program (22 points)Read the following algorithm and answer the following questions: (4)Perfect the program, and answer what the algorithm does? What is the function of r [n + 1] in the algorithm?Void sort (elemtype r [], int n)(int k, I;For (k = n minus 1; k > 二1; k -)・If (r [k] > r [k + 1]){r [n + 1]二r [k];，，For，z (I 二k + 1; r [I] < r [n + 1] ; I + +)R [I - 1] = r [I}}Complete the following program and say what the algorithm does(8)Void weizhisort (struct node r [n], int n)(int low, high, mid, j, I;For (I 二2; I 〈二n; I++){r[0]二r [I];Low 二________ ;High 二...Wh订e (low < = high)Well, it's going to be (1 ow + high) / 2; If (r[0]. Key < r [mid]. Key)Else low 二mid + 1; }For (j 二I - 1).R [j + 1]二T [j]；R [high + 1] = r [0];}The data type is defined as:Struct node(int key：Infotypes otherinfo;3, say what the algorithm does(2 points)Void delete (int a [n], int I){if (I < 0) > =n) printf (〃error 〃);The else (j 二i-1； j 〈n; j + +)A [j]二 a [j + 1];N is equal to n minus 1; } }Improve the program to show its function (8 points)# define NULL 0;Typedef struct Bitnode {Char data;Struct Bitnode * lchild・} Bitreptr;Void inorder_notrecursive (Bitreptr bt, Status (TelemType e)) {InitStack (S):P 二T;While (P | |! StackEmpty (s)){if (P) {Push (S, P);;The else {If (! (p-> data)) return Error;} return OK;A book, like a ship, leads us from a narrow place to an infinite sea of life, caleb。

XXX大学2020-2021学年第一学期计算机科学与技术专业《数据结构》期末考试题及答案（试卷B）一、填空题（每空1.5分，共30分）。

⒈任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的。

⒉数据结构是一门研究的程序设计问题中计算机的操作对象以及它们之间的等等的学科。

⒊带头结点的单向链表L为空的判定条件是；非空的循环单链表head的尾结点p满足条件。

⒋栈和队列是两种特殊的线性表，栈的特点是，栈的典型应用有和。

⒌在具有n个单元的循环队列中，队列满时共有个元素。

⒍若串的长度不能确定，可采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为。

⒎稀疏矩阵一般的压缩存储方法有两种，即和十字链表。

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

⒐一棵高度为h的满二叉树共有个终端结点。

⒑已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。

⒒具有8个顶点的有向完全图有条弧。

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

⒔对线性表进行二分查找时，要求线性表必须以方式存储，且结点按关键字排列。

⒕在分块查找方法中，首先查找索引，然后再查找相应的。

⒖与快速排序和堆排序相比，归并排序的最大特点是，它是一种的排序方法。

二、判断题（每小题1分，共10分）若正确，填入“T”，否则填入“F”。

⒈线性表的逻辑顺序与存储顺序总是一致的。

（）；⒉一个栈的入栈序列是12345，则栈的输出序列12345是不可能的。

（）；⒊将递归算法转换成对应的非递归算法时，通常需要使用栈。

（）；⒋设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。

（）；⒌二维数组是其数据元素为线性表的线性表。

（）；⒍线索二叉树是一种逻辑结构。

（）；⒎深度为K的完全二叉树至少有2K-1个结点。

班 姓 学 考试时 考场（教室装 线《数据结构》期末考试试卷(A)一、判断题：（正确者在括号内打“√”，错误者打“×”。

每小题1分，共10分）1．线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

（ ） 2．栈和队列是一种非线性数据结构。

（ ） 3．十字链表是无向图的一种存储结构。

（ ） 4．Hash 表的平均查找长度与处理冲突的方法无关。

（ ） 5．数据元素是数据的最小单位。

（ ） 6．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（ ） 7. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i 层上最多能有2i-1个结点。

（ ） 8．有e 条边的无向图，在邻接表中有e 个结点。

（ ） 9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（ ） 中插入一个新结点,总是插入到叶结点下面。

（ ） 二、选择题：（将每小题正确答案的选项填写在题后的横线上，每小题2分，共20分） x 的赋值语句的频度为___________。

FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A ． O(2n)B ．O(n)C ．O(n 2) D ．O(log2n) 2．下面关于串的的叙述中，哪一个是不正确的？___________。

A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 3．栈和队列的共同特点是___________。

A ．只允许在端点处插入和删除元素B ．都是先进后出C ．都是先进先出D ．没有共同点4．一个向量第一个元素的存储地址是50，每个元素的长度为4，则第5个元素的地址是___________。

A. 70 B. 66 C. 50 D. 785．设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为？___________。

“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。

A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。

A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。

4．在一棵高度为h的3叉树中，最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——·6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

广州轻工职业学校（大源校区）试卷用纸 第 1 页，共 1 页
专 班级 姓名 学号
注意：广州轻工职业学校（大源校区）
2015-2016学年第二学期《数据结构》期末考试试卷（B 卷）
注 意 事 项
1、请首先按要求在试卷的标封处填写您的专业、姓名、学号和所在的班级名称；
2、请仔细阅读各种题目的回答要求，在规定的位置填写您的答案；
3、不要在试卷上乱写乱画，不要在标封区填写无关内容。

使用对象：15计算机设计班 考试时间：45分钟 考试方式：考查
一、名词解释题（每小题5分，共35分）：
1. 顺序映像
2. 链式映像
3. 数据对象
4. 数据结构
5. 数据类型
6. 抽象数据类型
7. 算法
二、简答题（每小题10分，共30分）：
1. 数据元素与数据项有什么关系？
2. ADT 的特性有哪些？
3. 算法的特性有哪些？
三、论述题（共15分）：
在设计算法时，什么样的算法才是好的算法？
四、项目设计题（共20分）：
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N 块木头，每块木头长度为整数L 个长度单位。

于是他购买了一条很长的、能锯成N 块的木头，即该木头的长度是L 的总和。

但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。

为简单起见，不妨设酬金等于所锯木头的长度。

例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头将木头锯成12和8，花费20；第二次锯木头将长度为12的木头锯成
7和5花费12，总花费32.如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费35（大于32）.
请设计农夫将木头锯成N 块的最少花费。

《数据结构》期末考试试卷（ A ）一、选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据B.数据元素C.数据结构D.数据类型2．栈和队列都是（A）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串5．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100D. 1206．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为：CA. 2h B .2h-1C. 2h+1D. h+1软件开发网8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。

下列结论哪个正确？AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2D. 411．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（A）A．左子树的叶子结点B．左子树的分支结点C．右子树的叶子结点D．右子树的分支结点软件开发网12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )A.35和41B.23和39C.15和44D.25和51二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。

20XX ～20XX学年度第2学期《数据结构》期末考试课程代码：XXXXXX 试卷编号： 1 命题日期：20XX 年X 月X 日答题时限：120 分钟考试形式：闭卷笔试A/B卷： B 卷一、判断题（每小题1分，共10分）1．逻辑结构相同的数据，可以采用多种不同的存储方法。

（）2．如果单链表带有头节点，则插入操作永远不会改变头节点指针的值。

（）3．空栈没有栈顶指针。

（）4．递归算法不能转换成对应的非递归算法。

（）5．稀疏矩阵的特点是矩阵中元素较少。

（）6．树形结构中的每个节点都有一个前驱节点。

（）7．连通图的生成树包含了图中所有顶点。

（）8．最小生成树是指边数最少的生成树。

（）9．在平衡二叉排序树中，每个节点的平衡因子值都是相等的。

（）10．任何情况下归并排序都比直接插入排序快。

（）二、单项选择题（请从4个备选答案中选择最适合的一项，每小题1分，共20分）1．在数据结构中，从逻辑上可以把数据结构分为_________两类。

A ．动态结构和静态结构B ．紧凑结构和非紧凑结构C ．线性结构和非线性结构D ．内部结构和外部结构2．在链式存储结构中，通常一个存储节点用于存储一个_________。

A ．数据项B ．数据元素C ．数据结构D ．数据类型3．在一个长度为n 的顺序表中于第i 个元素（1≤i ≤n+1）之前插入一个新元素，需要向后移动_________个元素。

A ．n-iB ．n-i+1C ．n-i-1D ．i4．在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是_________。

A ．单链表B ．双链表C ．循环链表D ．顺序表5．设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是_________。

A ．A,B,C,DB ．D,C,B,AC ．A,C,D,BD ．D,A,B,C6．元素A 、B 、C 、D 依次进入队列qu 后，队尾元素是_________。

浙江财经学院东方学院2010～2011学年第一学期《数据结构》课程期末考试试卷（A 卷）考核方式：闭卷 考试日期：2010年 月 日 适用专业、班级：东方电子商务专业题 号 一 二 三 四 五 六 总分 得 分 评卷人（共六大题）说明：（1） 请考生将答案写在答题纸上； （2） 考试时间120分钟；一、单选题 （每题1分，共15分）1、对一个算法的评价，不包括如下（ ）方面的内容。

A ．健壮性B ．可读性C ．正确性D ．实用性 2执行下面程序段时，s 语句的执行次数为( D )。

for (int i=l; i<=n;i++) For(int j=1; j<=i; j++)S;A ．n2B ．N2／2C ．n(n+1) D.n(n+1)/2 3..下面算法的时间复杂度为(B) intf (int n){if (n==0 || n==l) return 1. Else return n*f(n-l);A ．O(1)B ．O(n)C ．O(n2)D O(n!)4、在一个长度为n 的顺序存储的线性表中，删除第i 个元素(1≤i ≤n)时，需要从前向后依次前移( A )个元素。

A. n-iB.n-i+1C.n-i-lD.i5若一个结点的引用为p ，在p 结点后面插入一个值为x 的新结点的操作为( D )。

A. p=new Node(x,p) B.p=new Node(x,p. next)密 封 线专业、班级： 学号： 姓名：C. p.next=new Node(x,p)D.p.next=new Node(x,p. next)6假定利用数组a顺序存储一个栈，用top表示栈顶指针，top-= -1表示栈空，并已知栈不为空，当退栈并返回栈顶元素时所执行的操作为( B )。

A.return a[- -top];B.return a[top--];C. rcturn a[++top];D.return a[top++];7若让元素1．2.3依次进栈．则出栈次序不可能出现( C )的情况。

数据结构期末考试试卷（A卷）第一学期开课单位：软件学院，考试形式：闭、开卷，允许带入场科目：数据结构班级：软件工程姓名：学号：题序一二三四五六七八九总分得分评卷人I. 基本概念部分（共60分）1 下图所示是单链表结点的插入过程，在fence结点后面插入一个值为10的ltmp结点，已知fence->next是指向fence的后继结点，请把这一插入过程用代码表示出来：(6分)这一过程的代码：ltmp->next = fence->next;fence->next = ltmp;2 下图所示是双链表结点的删除过程，在fence结点后面删除一个值为23的结点，已知fence->next是指向fence的后继结点，fence->prev是指向fence的前驱结点，ltmp是一个值为NULL的链表结点指针，请把这一删除过程用代码表示出来：(8分)这一过程的代码：ltmp = fence->next;fence->next = ltmp->next;ltmp->next->prev = fence;3 画出下图中的BST加上值5以后的形状。

(6分)4 画出下图所示图的相邻矩阵表示(假设下面的表格是一个二维数组,请在表格中填入正确的数值)。

(8分)1 2 3 4 5 61 10 20 22 103 53 3 154 205 11 105 15 11 36 2 10 35 给出下图从顶点1开始的DFS 树。

(8分)深度优先搜索（DFS ）：从底到高，从小到大 广度优先搜索（BFS ）：直接在下面的顶点中画出来即可：6 给出下图从顶点3开始使用Prim （普里姆）算法时的最小支撑树（最小生成树）。

(8分)32154 32154直接在下面的顶点中画出来即可：24 16357 起泡排序函数的算法如下：(8分)void bubsort(int A[], int n){int tmp;for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){if(A[i] > A[j]){tmp = A[i];A[i] = A[j];A[j] = tmp;}}//外层循环,打印一下中间结果for(int k = 0; k < n; k++) printf(" %d",A[k]);printf("\n");}}对数组int A[] = { 9, 12,3,7,90,15};应用上面的排序算法进行排序的部分中间打印结果如下，请补充使之完整：8 给出从下图的最大值堆中删除最大元素后得到的堆。