四川大学2021计算数据结构考试题2(含答案100分)

2022年四川大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-12、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。

2020-2021学年《数据结构》期末考试复习试题一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。

(A)、正确性(B). 可行性(C). 健壮性(D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。

for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A)、n2(B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377．图的Depth-First Search(DFS)遍历思想实际上是二叉树（）遍历方法的推广。

（A）、先序（B）、中序（C）、后序（D）、层序8．在下列链队列Q中，元素a出队的操作序列为（）（A）、p=Q.front->next; p->next= Q.front->next;（B）、p=Q.front->next; Q.front->next=p->next;（C）、p=Q.rear->next; p->next= Q.rear->next;（D）、p=Q->next; Q->next=p->next;9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值10．线索二叉链表是利用（）域存储后继结点的地址。

全国2021年10月数据结构试题及答案课程代码：02331第一部份选择题(30分)一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1．算法指的是（）A．计算机程序 B．解决问题的计算方式C．排序算法 D．解决问题的有限运算序列2．线性表采用链式存储时，结点的存储地址（）A．必需是不持续的B．持续与否都可C．必需是持续的D．和头结点的存储地址相持续3．将长度为n的单链表链接在长度为m的单链表以后的算法的时间复杂度为（） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由两个栈共享一个向量空间的益处是：（）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m6．如下陈述中正确的是（）A．串是一种特殊的线性表 B．串的长度必需大于零C．串中元素只能是字母 D．空串就是空白串7．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）A．O（） B．O（n） C．O（n2） D．O（n3）8．一个非空广义表的表头（）A．不可能是子表 B．只能是子表C．只能是原子 D．可以是子表或原子9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表0 2 3 3 5对应的稀疏矩阵是（）10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A．4 B．5 C．6 D．711．在含n个极点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e12．假设一个有n个极点和e条弧的有向图用邻接表表示,则删除与某个极点vi相关的所有弧的时间复杂度是( )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，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方式是（）A．选择排序 B．希尔排序 C．归并排序 D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表 B．分块有序表 C．三叉排序树 D．线性链表15．不定长文件是指（）A．文件的长度不固定 B．记录的长度不固定C．字段的长度不固定 D．关键字项的长度不固定第二部份非选择题（共70分）二、填空题（本大题共10小题，每小题2分，如有两个空格，每一个空格1分，共20分）不写解答进程，将正确的答案写在每小题的空格内。

数据结构与算法分析习题及参考答案四川⼤学《数据结构与算法分析》课程习题及参考答案模拟试卷⼀⼀、单选题（每题2 分，共20分）1.以下数据结构中哪⼀个是线性结构？( )A. 有向图B. 队列C. 线索⼆叉树D. B树2.在⼀个单链表HL中，若要在当前由指针p指向的结点后⾯插⼊⼀个由q指向的结点，则执⾏如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪⼀个不是队列的基本运算？（）A. 在队列第i个元素之后插⼊⼀个元素B. 从队头删除⼀个元素C. 判断⼀个队列是否为空D.读取队头元素的值4.字符A、B、C依次进⼊⼀个栈，按出栈的先后顺序组成不同的字符串，⾄多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶⼦⽣成⼀棵哈夫曼树，它的带权路径长度为( )。

A． 11 B.35 C. 19 D. 53以下6-8题基于图1。

6.该⼆叉树结点的前序遍历的序列为( )。

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该⼆叉树结点的中序遍历的序列为( )。

A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该⼆叉树的按层遍历的序列为( )。

EA GCB DF图1A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下⾯关于图的存储的叙述中正确的是( )。

A．⽤邻接表法存储图，占⽤的存储空间⼤⼩只与图中边数有关，⽽与结点个数⽆关B．⽤邻接表法存储图，占⽤的存储空间⼤⼩与图中边数和结点个数都有关C. ⽤邻接矩阵法存储图，占⽤的存储空间⼤⼩与图中结点个数和边数都有关D．⽤邻接矩阵法存储图，占⽤的存储空间⼤⼩只与图中边数有关，⽽与结点个数⽆关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下⾯哪⼀个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z⼆、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。

“数据结构”期末考试试题一、单选题(每小题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．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

2021年四川大学计算机科学与技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、假设相对寻址的转移指令占两个字节，第一个字节为操作码，第二个字节为位移量（用补码表示），每当CPU从存储器取出一个字节时，即自动完成（PC）+l-PC。

若当前指令地址是3008H，要求转移到300FH，则该转移指令第二个字节的内容应为（）；若当前指令地址为300FH，要求转移到3004H，则该转移指令第二字节的内容为（）。

A.05H，F2HB.07H，F3 HC.05H，F3HD.07H，F2H2、直接寻址的无条件转移指令的功能是将指令中的地址码送入（）。

A.程序计数器（PC）B.累加器（ACC）C.指令寄存器（IR）D.地址寄存器（MAR）3、并行加法器中，每位全和的形成除与本位相加两数数值位有关外，还与（）有A.低位数值大小B.低位数的全和C.高位数值大小D.低位数送来的进位4、若x=103，y=-25，则下列表达式采用8位定点补码运算时，会发生溢出的是（）。

A.x+yB.-x+yC.x-yD.x-y5、信息序列16位，若想构成能纠正一位错、发现两位错的海明码，至少需要加（）位校验位。

A.4B.5C.6D.76、设存储器容量为32字，字长为64位。

模块数m=4，采用低位交叉方式。

存储周期T=200ns，数据总线宽度为64位，总线传输周期r=50ns。

该交叉存储器的带宽是（）。

A.32×107bit/sB.8×107bit/sC.73×107bit/sD.18×107bit/s7、假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用写回（Write Back）方式，则能存放4K字数据的Cache的总容量的位数至少是（）。

A.146KB.147KC.148KD.158K8、下列关于配备32位微处理器的计算机的说法中，正确的是（）。

四川大学《数据结构》课程设计实验项目及内容提要(实验任选一个完成)
试读3页
数据结构实验报告
实验名称： Huffman编码(二叉树应用)
提交文档学生姓名：
提交文档学生学号：
同组成员名单：无
指导教师姓名：
指导教师评阅成绩：
指导教师评阅意见：
.
.
提交报告时间： 2020 年 3 月 26 日
目录
一、概述 (1)
二、系统分析 (1)
三、概要设计 (2)
四、详细设计 (4)
4.1 赫夫曼树的建立 (4)
4.1.1 选择选择parent 为0 且权值最小的两个根结点的算
法 (5)
4.1.2 统计字符串中字符的种类以及各类字符的个数 (7)
4.1.3构造赫夫曼树 (8)
4.2赫夫曼编码 (10)
4.2.1赫夫曼编码算法 (10)
4.2.2建立正文的编码文件 (11)
4.3代码文件的译码 (12)
五、运行与测试 (14)
六、总结与心得 (14)
参考文献................................. 错误!未定义书签。

附录..................................... 错误!未定义书签。

四川大学“精品课程”计算机科学与技术专业（本科）《数据结构与算法分析》课程考试说明与模拟试卷第一部分考试说明数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。

由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++开发工具（如：Visual C++或C++ Builder或Borland C++）。

下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。

第一章绪论重点掌握的内容：1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。

2. 集合结构、线性结构、树结构和图结构的特点。

3. 抽象数据类型的定义和表示方法。

4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。

5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。

6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。

7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。

8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。

对于本章的其余内容均作一般掌握。

第二章线性表重点掌握的内容：1. 线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。

3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。

4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。

四川大学期末考试试题（2007-2008学年第1学期）课程号：课程名称：数据结构与算法分析（A卷）任课教师：适用专业年级：06级软件工程学号：姓名：（1）An algorithm must be or do all of the following EXCEPT:a) correctb) composed of concrete stepsc) ambiguousd) composed of a finite number of steps（2）For set P, the notation |P| indicatesa) The number of elements in P. b) The inverse of P.c) The powerset of P. d) None of the above.（3）Pick the quadratic growth rate.a) 5n b) 20 log nc) 2n^2 d) 2^n（4）For set P, the notation |P| indicatesa) The number of elements in P.b) The inverse of P.c) The powerset of P.d) None of the above.（5）Huffman coding provides the optimal coding when:a) The messages are in English.b) The messages are binary numbers.c) The frequency of occurrence for a letter is independent of its context within the message.d) Never.（6）A sorting algorithm is stable if it:a) Works for all inputs.b) Does not change the relative ordering of records with identical key values.c) Always sorts in the same amount of time (within a constant factor) for a given input size. （7）Here is a series of C++ statements using the list ADT in the book.L1.append(10);L1.append(20);L1.append(15);If these statements are applied to an empty list, the result will looklike:a) < 10 20 15 >b) < | 10 20 15 >c) < 10 20 15 | >d) < 15 20 10 >e) < | 15 20 10 >f) < 15 20 10 | >（8）An entry-sequenced file stores records sorted by:a) Primary key value. b) Secondary key value.c) Order of arrival. d) Frequency of access.（9）Breadth-first search is best implemented using:a) A stack or recursion. b) A queue.c) A tree.（10）A recurrence relation is often used to model programs witha) for loops. b) branch control like "if" statements.c) recursive calls. d) None of the above.2．（10 scores）Assume a list has the following configuration:<| 6, 28, 16, 8, 9>Write a series of C++ statements using the List ADT as follows to delete the element with value 16.// List abstract classtemplate <class Elem> class List {public:// Reinitialize the list. The client is responsible for// reclaiming the storage used by the list elements. virtual void clear() = 0;// Insert an element at the front of the right partition.// Return true if successful, false if the list is full. virtual bool insert(const Elem&) = 0;// Append an element at the end of the right partition.// Return true if successful, false if the list is full. virtual bool append(const Elem&) = 0;// Remove the first element of right partition. Return// true if successful, false if right partition is empty.// The element removed is returned in the parameter. virtual bool remove(Elem&) = 0;// Place fence at list start, making left partition empty virtual void setStart() = 0;// Place fence at list end, making right partition empty virtual void setEnd() = 0;// Move fence one step left; no change if already at start virtual void prev() = 0;// Move fence one step right; no change if already at end virtual void next() = 0;// Return length of left partitionvirtual int leftLength() const = 0;// Return length of right partitionvirtual int rightLength() const = 0;// If pos or more elements are in the list, set the size// of left partition to pos and return true. Otherwise,// do nothing and return false.virtual bool setPos(int pos) = 0;// Return in first parameter the first element of the// right partition. Return true if successful, false// if the right partition is empty.virtual bool getV alue(Elem&) const = 0;// Print the contents of the listvirtual void print() const = 0;};3．（10 scores）Build the Huffman coding tree and determine the codes for the following set of letters and weights:a e i o u.1 3 5 7 84．（15 scores）Show the max-heap that results from running buildHeap on the following values stored in an array:10 5 12 3 2 1 8 7 9 45．（15 scores）When implementation Insertion Sort, a binary search could be used to locate the position within the first i – 1 elememts of the array into which element i should be inserted. How would this affect the number of comparisons required? How would using such a binary search affect the asymptotic running time for Insertion Sort?6．（15 scores）// Binary tree node abstract classtemplate <class Elem> class BinNode {public:// Return the node's elementvirtual Elem& val() = 0;// Set the node's elementvirtual void setV al(const Elem&) = 0;// Return the node's left childvirtual BinNode* left() const = 0;// Set the node's left childvirtual void setLeft(BinNode*) = 0;// Return the node's right childvirtual BinNode* right() const = 0;// Set the node's right childvirtual void setRight(BinNode*) = 0;// Return true iff the node is a leafvirtual bool isLeaf() = 0;};Write a recursive function that returns the height of a binary true..7．（15 scores）List the order in which the edges of the following graph are visited when running Prim’s MST algorithm starting3at V ertex 3. Show the final MST.。

数据库一.单选题（共39题,58.5分）1在SQL语句中,表达式“工资BETWEEN 1200 AND 1250”的含义是•A、工资> 1200 AND 工资<1250•B、工资> 1200 OR 工资<1250•C、工资> =1200 AND 工资<=1250•D、工资> =1200 OR 工资<=1250正确答案： C答案解析：2要为当前表所有职工增加100元工资,正确的SQL命令是命令•A、CHANGE 职工SET 工资=工资+100•B、REPLACE 职工SET 工资=工资+100•C、EDIT 职工SET 工资=工资+100•D、UPDATE 职工SET 工资=工资+100正确答案： D答案解析：3如下SQL语句Select avg(工资),单位名 from 职工 where 单位号 in (select 单位号 from 单位where 单位名=”设计所”)查询结果为•A、2000.00•B、1833.33•C、2100.00•D、3000.00正确答案： B答案解析：4在浏览窗口中,不能将一条记录逻辑删除的操作是( )•A、将光标定位于该记录,按Ctrl+T键•B、将光标定位于该记录,按DELECT键•C、将光标定位于该记录,单击表菜单中的“切换删除标志”选项•D、单击该记录前的白色小方块,使其变黑。

正确答案： B答案解析：5删除表的SQL命令是•A、DROP TABLE•B、DELETE TABLE•C、ERASE TABLE•D、KILL TABLE正确答案： A答案解析：6有SQL语句:SELECT MIN(工资)FROM 职工的执行结果是•A、工资的最大值•B、工资的最小值•C、工资的平均值•D、工资的合计正确答案： B答案解析：7在SQL语句中用于限定条件的短语是•A、FOR•B、WHILE•C、WHERE•D、CONDITION正确答案： C答案解析：8Delete的作用是•A、将记录从表中彻底删除•B、只给要删除的记录做删除标志•C、不能删除记录•D、删除整个表中的记录正确答案： B答案解析：9在Foxpro6.0中,打开数据库使用的命令为( )•A、USE•B、SELECT•C、OPEN•D、CREATE正确答案： C答案解析：10要为当前表所有商品价格上调8%,正确的SQL命令是命令( )。