下载文档原格式
数据结构c语言期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。
A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一关系D. 结构中元素之间是否有一对多关系答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。
A. i-1B. n-iC. n-i+1D. n-i-1答案：B4. 栈的运算遵循（）原则。
A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C5. 在二叉树的前序遍历中，访问顺序为（）。
A. 根-左-右B. 左-根-右C. 左-右-根D. 右-左-根答案：A6. 哈希表的冲突解决方法中，链地址法是（）。
A. 将所有元素存储在同一个存储单元B. 将所有元素存储在同一个链表中C. 将所有元素存储在同一个数组中D. 将所有元素存储在同一个链表的同一个位置答案：B7. 在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。
A. 遍历的顺序不同B. 遍历的起点不同C. 遍历的路径不同D. 遍历使用的存储结构不同答案：D8. 快速排序算法的时间复杂度为（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B9. 归并排序算法的时间复杂度为（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 在二叉搜索树中，查找一个元素的时间复杂度为（）。
A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度通常用______来描述。
答案：大O符号2. 线性表的两种基本操作是插入和______。
数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。
A. 执行算法所需要的计算工作量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。
A. 插入和删除操作快B. 存储密度高C. 存储空间可以动态分配D. 存储空间利用率高答案：B3. 栈的基本运算中，不包括（）。
A. 入栈B. 出栈C. 取栈顶元素D. 排序答案：D4. 在二叉树的遍历中，先序遍历的顺序是（）。
A. 先根后子B. 先子后根C. 先左后右D. 先右后左答案：A5. 哈希表解决冲突的方法不包括（）。
A. 分离链接法B. 线性探测法C. 链地址法D. 二分查找法答案：D6. 一个图的邻接矩阵表示法中，若第i行第j列的元素为1，则表示（）。
A. 顶点i和顶点j之间有一条边B. 顶点i和顶点j之间没有边C. 顶点i和顶点j之间有n条边D. 顶点i和顶点j之间有m条边答案：A7. 在查找算法中，二分查找法适用于（）。
A. 线性表B. 哈希表C. 树形结构D. 图结构答案：A8. 快速排序算法的时间复杂度在最坏情况下是（）。
A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C9. 一个有n个顶点的无向图，其边数最多为（）。
A. nB. n(n-1)/2C. n(n+1)/2D. 2n答案：B10. 以下哪个不是排序算法（）。
A. 冒泡排序B. 选择排序C. 插入排序D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中所需要的___________。
答案：存储空间2. 线性表的链式存储结构中，每个节点包含___________和___________。
答案：数据元素，指针3. 栈的特点是___________，___________。
2005-12-19准备题填空题1．顺序表、栈和队列都是_______结构，可以在顺序表的_______位置插入和删除元素；对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素和_______删除元素。
2．由头指针head指向的非空循环单链表，尾结点为p，则head和p满足条件_______________。
3．共H层的完全二叉树至少有个结点，至多有个结点，若按自上而下、从左到右次序给结点编号（从0开始），则编号最小的叶子结点的编号是_________。
4．n个顶点的连通图至少有条边。
5．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于6．任何一个具有n个结点的无向图的边数小于或等于_______________。
7．任何一个具有n个结点的完全有向图的边数为_______________。
8．排序方法的稳定是指___________________________________。
9．根据数据元素之间的关系，数据在计算机中的存储有两种不同的存储结构，分别是：______存储结构和______存储结构。
10．在数据结构中，数据元素之间通常有下列四类基本结构：______、________、_______和________。
11．通过衡量一个算法的______复杂度和______复杂度来进行判定一个算法的好坏。
12．线性表的最主要的两种应用是______和______，它们之间最重要的区别是：一个是__________、另一个是__________。
13．m*n的稀疏矩阵中，有t个元素不为零，则该矩阵的稀疏因子为______，对于稀疏矩阵，我们通常对其进行______存储。
14．字符串的五种基本操作是：串______、串______、______、串______和______。
15．在二叉树的链式存储结构中，n个结点的二叉链表中有______个空链域。
数据结构期末考试试题及答案一、选择题1. 评价一个算法时间性能的主要标准是( )。
A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（）等五个特性。
A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（）。
A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4. 以下关于线性表的说法不正确的是( )。
A、线性表中的数据元素可以是数字、字符、记录等不同类型。
B、线性表中包含的数据元素个数不是任意的。
C、线性表中的每个结点都有且只有一个直接前趋和直接后继。
D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。
5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。
A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( )运算中，使用顺序表比链表好。
A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（）个元素A、n-iB、n-i+1C、n-i-1D、i8. ( )适合作为经常在首尾两端操作线性表的存储结构。
A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。
A、4 3 2 1B、1 2 3 4C、1 4 3 2D、3 2 4 111. 队列与一般的线性表的区别在于( )。
A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在( )中。
A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。
2022年北京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f, dD.a，e，d，f，c，b2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13B.33C.18D.403、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。
A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
2022年北京邮电大学网络工程专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、"从中间开始"设计的"中间"目前多数是在( )。
A.传统机器语言级与操作系统机器级之间B.传统机器语言级与微程序机器级之间C.微程序机器级与汇编语言机器级之间D.操作系统机器级与汇编语言机器级之间2、全相联地址映象是指（）。
A.任何虚页都可装入主存中任何实页的位置B.一个虚页只装进固定的主存实页位置C.组之间是固定的，而组内任何虚页可以装入任何实页位置D.组间可任意装入，组内是固定装入3、与流水线最大吞吐率高低有关的是( )A.各个子过程的时间B.最快子过程的时间C.最慢子过程的时间D.最后子过程的时间4、浮点数尾数基值rm=8，尾数数值部分长6位，可表示的规格化最小正尾数为( )A.0.5B.0.25C.0.125D.1/645、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断6、外部设备打印机适合于连接到( )。
A.数组多路通道B.字节多路通道C.选择通道D.任意一种通道7、对系统程序员不透明的应当是( )。
A.Cache存贮器XB.系列机各档不同的数据通路宽度C.指令缓冲寄存器D.虚拟存贮器8、下列说法正确的是( )A.Cache容量一般不大，命中率不会很高B.Cache芯片速度一般比CPU的速度慢数十倍C.Cache本身速度很快。
但地址变换的速度很慢D.Cache存贮器查映象表和访问物理Cache其间可以流水，使速度与CPU匹配9、在多用户机器上，应用程序员不能使用的指令是（）A.“执行”指令B.“访管”指令C.“启动IO”指令D“测试与置定”指令10、“启动I/O”指令是主要的输入输出指令，是属于（）。
A.目态指令B.管态指令C.目态、管态都能用的指令D.编译程序只能用的指令二、判断题11、软硬功能分配时，提高软件功能的比例会提高系统灵活性，也会提高解题速度。
数据结构c语言期末考试试题及答案一、选择题（每题2分，共20分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 在C语言中，以下哪个函数用于创建链表节点？A. mallocB. callocC. reallocD. free答案：A3. 如果一个链表的头指针为NULL，这意味着什么？A. 链表为空A. 链表已满C. 链表正在使用中D. 链表已损坏答案：A4. 在C语言中，以下哪个数据结构允许快速随机访问？A. 链表B. 数组C. 栈D. 队列5. 在二叉树中，以下哪个术语描述了没有子节点的节点？A. 根节点B. 叶节点C. 内部节点D. 父节点答案：B6. 以下哪个算法用于在二叉搜索树中查找一个元素？A. 深度优先搜索B. 广度优先搜索C. 插入排序D. 二分查找答案：D7. 在C语言中，以下哪个关键字用于定义一个函数？A. intB. voidC. returnD. struct答案：A8. 以下哪个选项是正确的递归函数定义？A. int fact(int n) { if (n > 1) return n * fact(n-1); else return 1; }B. int fact(int n) { if (n > 1) return n * fact(n); else return 1; }C. int fact(int n) { if (n > 1) return n * fact(n+1); else return 1; }D. int fact(int n) { if (n > 1) return n; else return 1; }9. 在C语言中，以下哪个函数用于释放动态分配的内存？A. mallocB. callocC. reallocD. free答案：D10. 在C语言中，以下哪个关键字用于定义一个指针？A. intB. charC. *D. &答案：C二、填空题（每题2分，共20分）1. 在C语言中，结构体的成员可以通过其结构体变量名和______访问。
2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分）1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）A.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（）A.543612B.453126C.346512D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（）A.8B.9C.10D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（）A. m-nB.m-n-1C.n+1D.m+n5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9B.11C.15D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。
（）A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。
A.73B.234C.235D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1分，共15分）1.数据结构中评价算法的两个重要指标是、空间复杂度。
《数据结构》试题答案A卷姓名班级一、回答下列问题 (每题5分，共40分)1．给定序列（67，45，87，19，55，32，70，60，90，23），写出它的初始堆序列。
答：调整后的初始堆序列(小根堆)为：19，23，32，45，55，87，70，60，90，67或者是大根堆：90, 67, 87, 60, 55, 32, 70, 45, 19, 232．设一个序列奇数项和偶数项分别由小到大有序，用什么方法可以最快得到一个有序序列，分析它的时间复杂度。
答：把奇数项和偶数项分为2个有序序列，然后进行合并，时间复杂度为O(n)。
实际上就是把2个有序表合并为一个有序表。
见教科书算法2.7。
3．二叉排序树中的最大值在二叉排序树的何处？答：最大值应该位于二叉排序树中根的右子树的最右叶子上。
1923 3245 55 7060 904．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序是否比用锦标赛排序更快？为什么？答：此题用锦标赛排序比堆排序要快。
理由是；①在首次求最小值时，锦标赛排序对2048个结点建树得到最小码只需比较n-1(即2047)次，而此时堆排序建初始堆得到最小码却可能需要比较4072次(因为每个结点的调整都要与左右两边的孩子相比。
从第1024个结点往前调整，有512个结点可能调整1次，但要与左右孩子都比较，有256个结点可能调整2次，每次都要与左右孩子比较，有128个结点可能调整3次，……有32个结点调整5次，……根结点可能要调整10次，每次都会与左右孩子比较，所以可能会比较2036×2=4072次)。
而两种算法对求后面4个次小码的平均效率相同，都是log2n，所以，此题用锦标赛排序会比堆排序快。
5．n个顶点、m条边的全连通图，至少去掉几条边才能构成一棵树？答：因为树的结构是一对多，即n个结点的树只有n-1条边与双亲结点相连。
只要再多添一条边就会成为图结构。
所以，m条边的图要去掉m-(n-1)=m-n+1条边才能构成一棵树。
O S TEST1．Fill in the blanks with the proper words.( 10 cents)1. Operating system is a program that acts as an intermediary between _____ and______.2.To prevent user programs from interfering with the proper operation of the system,the hardware has two modes: _________, __________.3.___________ is the separation of user ______ from physical memory. User wouldbe able to write programs for an extremely large __________ space, simplifying the programming task.4.The file system consists of two distinct parts: _______, each storing related dataand _______, which organizes and provides information about all the files in the system.5.System call provide the interface between _____ and _____ .6.________ provide an object-oriented way of implementing file systems, and itallows the same system call interface (the API) to be used for different types of file systems.7. A process is a program in execution. A process needs certain resources, including____, ______, files, and ______ to accomplish its task.8.Disk-scheduling algorithms can improve _________, _________, and ________.9.The primary distinction between long-term scheduler and short-term scheduler is_______.10.The device drivers present a uniform device-access interface to ______ , much assystem calls provide a standard interface between the application and the operating system.2. Choose the best answer, and each blank has one answer. (23 cents) 1. Operating system is a kind of(1) , (2) is not the main problem it handles.(1). A. Application software;B. System software;C. Common software;D. Software package;(2). A. managing the bar-machine;B. designing, providing the interface between user program and hardwaresystem;C. managing the information resource of the computer;D. the compiling of the high-level program-designing language.2. The utilization of the memory can be improved by __(1)___. Its basic task is__(2)_ for each program; and each program can run safely and separately, main by __(3)____.(1), (3): A. memory-allocating B. memory-protectingC. address-mappingD. swapping(2): A. the diversion from logical address to physical addressB. the swapping between memory and backing store;C. the address space of the user’s applications can be larger than the memoryspace;D. allocation the memory.3. The response time of time-sharing system depends on_(1)___; while the response time of the real-time system depends on __(2)__.A. the size of time quantum;B. the number of users;C. the speed of the computer;D. the waiting time the users can accept;E. the time delay the object controlled can accept;F. the real-time scheduling.4. In a single-processor system, there are 5 processes, then _(1)___ processes can be in the ready queue, __(2)__ processes can be in the waiting queue.A. 5 ;B. 4;C. 3;D. 2;E. 1;F. 0;5. In the producer-consumer problem, the mutex-semaphore mutex, the resource-semaphore full and empty. Their initial value are 1, _(1)____ and __(2)__ respectively.A. 0;B. 1;C. 1;D.-1;E.-n;F. +n.6. The maximum capacity of the virtual storage of a computer system depends on __(1)____, and the pratical capacity depends on __(2)____.A. the length of the computer word;B. the memory capacity;C. the capacity of the hard disk;D. the capacity of the memory and disk;E. the address structure of the computer;7. The basic intention of the file system is _(1)__, and it can be realized by __(2)_, and the most important intention of the file system is _(3)__.A. accessing files by names;B. directory-managing;C. file-protecting;D. boost the speed of the file-accessing;E. improve the utilization of storage;8. In the algorithms below, __(1)____ can only be implemented by the nonpreemptive method, __(2)__ can only be implemented by preemptive method, while the rest can be implemented by both.A. Priority scheduling;B. Round-Robin scheduling;C. FCFS scheduling;D. Shortest-Job-First scheduling.9. Suppose there are 10 processes in the ready queue, with round-robin scheduling, the time quantum is 300 ms, and the CPU-switch costs 10 ms, then the percent of the system spending is about__(1)___; if the number of the processes in the ready queue adds up to 20, the percent will __(2)___.(1): A. 1%; B. 3%; C.5%; D. 10%; E. 30%;(2): A. increase; B. decrease; C. not change.10. When looking up a file by hash-table, you find the according directory item isempty , and this represents __(1)_; if the file name in that directory matches the file name you are looking up, it represents__(2)__; if it doesn’t match, it represents _(3)__.A. the file name has been modified;B. there is no file name you are searching in the system;C. new file just created;D. it is a collision;E. you has the accessing right;F. you find the right file;3. Please answer the questions given below.1.What are the differences between a process and a thread? Please draw the diagramof the process states。
