计算机学科专业基础综合数据结构

1、法的出栈序列。
（分数：2.00）A.5 4 3 6 1 2B.4 5 3 1 2 6C.3 4 6 5 2 1D.2 3 4 1 5 63.若一个栈的输入序列为 1，2，3，n，输出序列的第一个元素是 i，则第 j个输出元素是 _ 。
（分数：2.00）A.i-j-1B.i-jC.j-i+1D.不确定的4.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时 _ 。
（分数：2.00）A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针都可能要修改5.假设以行序为主序存储二维数组 Aarray1100，1100，设每个数据元素占 2个存储单元，基地址为 10，则 LOC5，5= _ 。
（分数：2.00）A.808B.818C.1010D.10206.设有一个 10阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8，5的地址为 _ 。
（分数：2.00）A.13B.33C.18D.407.假设按低下标优先。

2、00）A.B.C.D.2.用 S表示进栈操作，用 X表示出栈操作，若元素的进栈顺序是 1，2，3，4，为了得到出栈顺序1，3，4，2，相应的 S和 X的操作序列为_。
A.SXSXSSXX B.SSSXXSXX C.SXSSXXSX D.SXSSXSXX（分数：1.00）A.B.C.D.3.已知一个栈的进栈序列为 1，2，3，n，其输出序列的第一个元素是 i，则第 j个出栈元素是_。
A.j-i B.n-i C.j-i+1 D.不确定（分数：1.00）A.B.C.D.4.已知一个栈的进栈序列为 1，2，3，n，其输出序列是 p1，p 2，p 3，p n。
若 p1=3，则 p2的值_。
A.一定是 2 B.一定是 1 C.可能是 1 D.可能是 2（分数：1.00）A.B.C.D.5.已知一个栈的进栈序列为 p1，p 2，p 3，p n，其输出序列是 1，2，3，n。
若 p3=1，则 p1的值_。
A.一定是 2 B.可能是 2 C.不可能是 2 D.一定是 3（分。

3、数：2.00）A.n-iB.n-i+1C.n-i-1Di3.在一个长度为 n 的顺序表中向第 i 个元素(0in+1)之前插入一个新元素时，需向后移动( )个元素。
（分数：2.00）A.n-iB.n-i+1C.n-i-1Di4.下述哪一条是顺序存储结构的优点? _（分数：2.00）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示5.下面关于线性表的叙述中，错误的是哪一个? _（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作6.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 _ 存储方式最节省时间。
（分数：2.00）A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表7.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为 _ 。
（分数：2.00）A.O(n)，O(n)B.O(n)，O(1)C.O(1)，O(n)D.O(1。

4、00）A.B.C.D.2.已知两个长度分别为 l 和 s 的降序链表，若将它们合并为一个长度为 l+s 的升序链表，则最坏情况下的时间复杂度是_。
A.O(l) B.O(ls) C.O(min(l，s) D.O(max(l，s)（分数：2.00）A.B.C.D.3.线性表中存放的主要是_。
A.整型常量 B.字符 C.数据元素 D.信息元素（分数：2.00）A.B.C.D.4.下面的叙述中正确的是_。
线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比 A.仅 B.仅 C.仅 D.、（分数：2.00）A.B.C.D.5.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择_存储方式最节省时间。
A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表（分数：2.00）A.B.C.D。

5、次数为( 2 )，二分法查找只适用于查找顺序存储的有序表，平均比较次数为( 3 )。
在此假定 N为线性表中结点数，且每次查找都是成功的。
A.N+1 B.2log2N C.log2N D.N/2 E.Nlog2N F.N2（分数：2.00）A.B.C.D.E.F.A.B.C.D.E.F.2.适用于折半查找的表的存储方式及元素排列要求为_。
（分数：1.00）A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序3.具有 12个关键字的有序表，折半查找的平均查找长度为_。
（分数：1.00）A.3.1B.4C.2.5D.54.折半查找的时间复杂性为_。
A.O(n2) B.O(n) C.O(nlog2n) D.O(log2n)（分数：1.00）A.B.C.D.5.当采用分块查找时，数据的组织方式为_。
（分数：1.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每。

6、对线性表进行折半查找时，要求线性表必须_。
A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序（分数：1.00）A.B.C.D.3.采用折半查找方式查找一个长度为 n的有序顺序表时，其平均查找长度为_。
A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n)（分数：1.00）A.B.C.D.4.在对长度为 n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为_。
An BC D （分数：1.00）A.B.C.D.5.采用折半查找法查找长度为 n的有序顺序表，查找每个元素的数据比较次数_对应二叉判定树的高度(设高度2)。
A.小于 B.大于 C.等于 D.小于等于（分数：1.00）A.B.C.D.6.已知有序顺序表(13，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找值为 18的元素时，查找成功的数据比较次数为_。
A.1 B.2 。

7、路归并排序D.冒泡排序3.下列内部排序算法中，在初始序列已基本有序(除去 n个元素中的某 k个元素后即呈有序，kn)的情况下，排序效率最高的算法是_。
（分数：1.00）A.冒泡排序B.堆排序C.直接插入排序D.二路归并排序4.下列排序算法中，_每一趟都能选出一个元素放在最终位置上，并且是不稳定的。
（分数：1.00）A.冒泡排序B.希尔排序C.简单选择排序D.直接插入排序5.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(log 2 n)的是_。
（分数：1.00）A.堆排序B.冒泡排序C.直接选择排序D.快速排序6.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是_。
（分数：1.00）A.选择排序B.冒泡排序C.归并排序D.堆排序7.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是_。
（分数：1.00）A.直接插入排序B.归并排序C.直接选择排序D.堆排序对初始状态为递增序列的表按递增顺序排序，最省时间的是( 8 )算法，最费时间的是( 9 )算法。
A.堆。

8、 A.5 B.6 C.7 D.8（分数：1.00）A.B.C.D.3.下列关于无向连通图特性的叙述中，正确的是_。
所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1 A.只有 B.只有 C.和 D.和（分数：1.00）A.B.C.D.4.对于具有 n(n1)个顶点的强连通图，其有向边的条数至少是_。
A.n+1 B.n C.n-1 D.n-2（分数：1.00）A.B.C.D.5.下列有关图的说法中正确的是_。
A.在图结构中，顶点不可以没有任何前驱和后继 B.具有 n个顶点的无向图最多有 n(n-1)条边，最少有 n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和（分数：1.00）A.B.C.D.6.对于一个具有 n个顶点和 e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是_，矩阵中非零元素的个数是 2e。
A.n B.(n-1)2 C.n-1 D.n2（分数：1.00）A.B.。

9、数目U /U。
A.n*n B.n(n+1) C.n/2 D.n*(n-1)（分数：2.00）A.B.C.D.3.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为U /U。
A.O(n) B.O(n+e) C.O(n2) D.O(n3)（分数：2.00）A.B.C.D.4.若一个图的边集为(A，B)， (A，C)， (B，D)， (C，F)， (D，E)， (D，F)，则从顶点 A开始对该图进行广度优先搜索，得到的顶点序列可能为U /U。
A.A，B，C，D，E，F B.A，B，C，F，D，E C.A，B，D，C，E，F D.A，C，B，F，D，E（分数：2.00）A.B.C.D.5.已知有向图 G=(V，E)，其中 V=V1，V2，V3，V4，V5，V6，V7，E=V1，V2，V1，V3，V1，V4，V2，V5，V3，V5，V3V6，V4，V6，V5，V7，V6，V7)，G 的拓扑序列是U /U。
A.V1。

10、A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10D.75，45，65，10，25，30，20，153.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 _ 。
（分数：2.00）A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，84，56，79)4.数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中 _ 的两趟排序后的结果。
（分数：2.00）A.选择排序B.冒泡排序C.插入排序D.堆排序5.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为 _ 。
(1)84 47 25 15 21 (2)1 5 47 25 84 21 (3)15 21 25 84 47 (4)1 5 21 25 47 84 则采用的排序是 _ 。
（分数：2.00）A.选择。

11、为 4的希尔排序一趟扫描的结果。
A.an，bai，deng，fang，li，shi，tang，wan B.an，tang，deng，wan，shi，bai，fang，li C.li，deng，an，shi，bai，fang，tang，wan D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C.D.2.以下关于希尔排序的说法中，正确的是_。
A.当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快 B.当待排序元素序列的初始排列基本逆序时，希尔排序比直接插入排序快 C.当待排序元素序列的初始排列基本有序时，希尔排序比起泡排序快 D.当待排序元素序列的初始排列基本逆序时，希尔排序比起泡排序慢（分数：2.00）A.B.C.D.3.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。
采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li)中的排序码按升序排列，则_是以第一个元素为分界元素的快速排序一趟扫描的结果。

12、的算法?_ A.Prim(普里姆)算法 B.Kruskal(克鲁斯卡尔算法) C.罗巴赫算法 D.其他算法（分数：1.00）A.B.C.D.2.邻接表是图的一种_。
A.顺序存储结构 B.链接存储结构 C.索引存储结构 D.散列存储结构（分数：1.00）A.B.C.D.3.下面试图对图中路径进行定义，说法正确的是_。
A.由顶点和相邻顶点序列构成的边所形成的序列 B.由不同顶点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是（分数：1.00）A.B.C.D.4.无向图中顶点个数为 n，那么边数最多为_。
A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.n2（分数：1.00）A.B.C.D.5.在一个具有 n(n0)个顶点的连通无向图中，至少需要的边数是_。
A.n B.n+1 C.n-1 D.n/2（分数：1.00）A.B.C.D.6.以下叙述中正确的是_。
对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能。

13、数为_，二分法查找只适用于查找顺序存储的有序表，平均比较次数为_。
在此假定 N 为线性表中结点数，且每次查找都是成功的。
（分数：4.00）A.N+1B.2log2NC.log2ND.N/2E.Nlog2NFN2A.N+1B.2log2NC.log2ND.N/2E.Nlog2NFN22.下面关于二分查找的叙述正确的是_。
（分数：2.00）A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型、实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储二叉查找树的查找效率与二叉树的_有天，在_时查找效率最低。
（分数：4.00）A.高度B.结点的多少C.树形D.结点的位置A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂3.当采用分块查找时，数据的组织方式为_。
（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索。

14、om(n)返回一个 0到 n-1之间的随机整数(包括 0与 n-1在内)。
（分数：10.00）(1).H(key)=key/n（分数：2.50）_(2).H(key)=1（分数：2.50）_(3).H(key)=(Key+random(n)%n（分数：2.50）_(4).H(key)=key%p(n)；其中 p(n)是不大于 n的最大素数（分数：2.50）_。

15、别设在这片内存空间的两端，这样，当 () 时，才产生上溢。
（分数：10.00）A空B满C.上溢D.下溢A空B满C.上溢D.下溢A.n-1BnC.n+1D.n/2A.长度B.深度C.栈顶D.栈底A.两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇D.两个栈均不空，且一个栈的栈顶到达另一个栈的栈底1.设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为_。
（分数：2.00）A.fedcbaB.bcafedC.dcefbaD.cabdef2.栈在_中应用。
（分数：2.00）A.递归调用B.子程序调用C.表达式求值D.以上都是3.表达式 a*(b+c)-d 的后缀表达式是_。
（分数：2.00）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd4.用链接方式存储的队列，在进行删除运算时_。
（分数：2.00）A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改5.设 A 是 nn 的对称矩阵，将 A 。

16、删除和查找2.在线性表中的每一个表元素都是数据对象，它们是不可再分的_。
（分数：2.00）A.数据项B.数据记录C.数据元素D.数据字段3.对于顺序存储的线性表，其算法的时间复杂度为 O(1)的运算应是_。
（分数：2.00）A.将 n 个元素从小到大排序B.从线性表中删除第 i 个元素(1in)C.查找第 i 个元素(1in)D.在第 i 个元素后插入一个新元素(1in)4.下面的叙述正确的是_。
（分数：2.00）A.线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关B.线性表在链式存储时，查找第 i 个元素的时间同 i 的值成反比C.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比D.线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关通常查找线性表数据元素的方法有 () 和 () 两种方法，其中 () 是一种只适合于顺序存储结构但 () 的方法；而 () 是一种对顺序和链式存储结构均适用的方法。
（分数：6.00）A.顺序查找B.循环查找C.条件查找D.折半查找A.顺序查找B.随机查找C.折半查找D.。

17、则此二叉树中所包含的结点个数至少有_；已知二叉树有 50个叶结点，有 30个度为 1的结点，则该二叉树的总结点数为_。
（分数：5.00）A.2d+1B.2d-1C.2d-1D.2d-1A.129B.130C.131D.1321.设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为 m1、m2 和 m那么在由该森林转化成的二叉树中根结点的右子树上的结点个数是_。
（分数：2.50）A.m1+m2B.m2+m3C.m3+m1D.m1+m2+m32.用 n个权值构造出来的 Huffman树的结点个数是_。
（分数：2.50）A.2n-1B.2nC.2n+1D.n+13.在下列关于二叉树遍历的说法中错误的是_。
（分数：2.50）A.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果B.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果C.在一棵二叉树中，假定每个结点最多只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则。

18、简单无向图，在其邻接矩阵中共有_个零元素，该邻接矩阵是一个_。
而用邻接矩阵存储有向图时某一个顶点 i 的入度等于该矩阵的_。
（分数：8.00）A.权值B.顶点C边D.边与顶点均AeB.2eC.n2-eD.n2-2eA.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵A.第 i 行中值为 1 的元素个数B.所有值为 1 的元素总是C.第 i 行及第 i 列中值为 1 的元素总个数D.第 i 列中值为 1 的元素个数图的深度优先搜索类似于树的_次序遍历，图的广度优先搜索类似于树的_次序遍历。
（分数：4.00）A.先根B.中根C.后根D.层次A.先根B.中根C.后根D.层次一个连通图的生成树是包含图中所有顶点的一个_子图。
n(n1)个顶点的强连通图中至少含有_条有向边。
（分数：4.00）A.极小B.连通C.极小连通D.无环A.n-1BnC.n(n-1)/2D.n(n-1)1.在一个带权连通图 G 中，权值最小的边一定包含在 G 的_生成树中。
（分数：2.00）A.最小B.任何C.广度优先D.深度优先在用 Dijk。

19、(2).从顺序表中删除第 i个元素并由函数返回被删元素的值。
如果 i不合理或顺序表为空则显示出错信息并退出运行。
（分数：4.00）_(3).向顺序表中第 i个位置插入一个新的元素 x。
如果 i不合理则显示出错信息并退出运行。
（分数：4.00）_(4).从顺序表中删除具有给定值 x的所有元素。
（分数：4.00）_(5).从顺序表中删除其值在给定值。

20、(2).编号为 i 的结点的父结点(若存在)的编号是多少?（分数：4.00）_(3).编号为 i 的结点的第 k 个子女结点(若存在)的编号是多少?（分数：4.00）_(4).编号为 i 的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?（分数：4.00）_(5).若结点个数为 n。