计算机专业基础综合数据结构数据和广义表

1、堆排序、快速排序、归并排序的关系是( )。
（A）堆排序快速排序归并排序（B）堆排序归并排序快速排序（C）堆排序归并排序快速排序（D）堆排序快速排序归并排序3 一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。
（A）16，25，35，48，23，40，79，82，36，72（B） 16，25，35，48，79，82，23，36，40，72（C） 16，25，48，35，79，82，23，36，40，72（D）16，25，35，48，79，23，36，40，72，824 已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。
（A）16，28，34，54，73，62，60，26，43，95（B） 28，16，34，54，62，73，60，26，43，95（C） 28，16，34，54，62，60，73，26，43，95（D）16，28，34，54，62，6。

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

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

4、2.采用简单选择排序，比较次数与移动次数分别为( )。
（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n)D.O(nlog 2 n)，O(n)3.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。
（分数：2.00）A.堆排序快速排序归并排序B.堆排序归并排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序4.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5 个长度为 2 的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。
（分数：2.00）A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，825.已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对。

5、简单无向图，在其邻接矩阵中共有_个零元素，该邻接矩阵是一个_。
而用邻接矩阵存储有向图时某一个顶点 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。

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

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

8、数：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。

9、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。

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

11、是( )。
【南京理工大学 1999 二、8(2 分)】（A）60（B） 66（C） 18000 （D）333 数组 A04，一 1-3，57中含有元素的个数( )。
【中山大学 1998 二、5(2 分)】（A）55（B） 45（C） 36 （D）164 用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使j 沿链移动的操作为( ) 。
【南京理工大学 2001 一、1 6(15 分)】（A）j=rfnext（B） j=1+1（C） j=f 一next （D）j=rj一next5 一个非空广义表的表尾( )。
【北京交通大学 2004 一、2(2 分)】（A）不能是子表（B）只能是子表（C）只能是原子（D）是原子或子表6 广义表(a)，(b ，(c) ，(e(e ，f) ，o)的深度是( )。
【华中科技大学 2007 一、7(2 分)】（A）2（B） 3（C） 4 （D）57 广义表(a，(b ，(c，d(e ，f) ，g)的深度为( ) 。
【北京邮电大学 2005 一、4(2 分)】（A）3（B） 。

12、从首地址 S 开始连续存放在主存储器中，主存储器字长为 16 位。
求：(1)存放该数组所需多少单元?(2)存放数组第 4 列所有元素至少需多少单元?(3)数组按行存放时，元素 A7，4 的起始地址是多少?(4)数组按列存放时，元素 A4，7 的起始地址是多少? 【大连海事大学 1996 四、1(6 分)】3 假设按低下标优先存储整型数组 A(一 3：8，3：5，一 4：0，0：7)时，第一个元素的字节存储地址是 100，每个整数占 4 字节，问 A(0，4，一 2，5)的存储地址是什么? 【清华大学 1996 三】4 设有五对角矩阵 A=(aij)20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组 A-10：m中，计算元素 A15，16的存储位置。
【东北大学 1999 一、2(4 分)】5 数组 A08，110】的元素是 6 个字符组成的串，则存放 A 至少需要多少字节?A 的第 8 列和第 5 行共占多少字节? 若 A 按行优先方式存储，元素 A8，5的起始地址与当 A 按列优先方式存储时的哪个元素的起始地址一致 ?【厦门大学 2000五、。

13、】（A）a，6，b，a（B） b，a，a，b（C） a，a，b，b（D）b ，a ，a，b E：a ，b ，b，a Fb，b，a，a2 广义表()的表头是( )，表尾是( )。
【电子科技大学 2003 一、4(208 分)】（A）O（B） NIL（C） (O)（D）(O)3 将线性表的数据元素进行扩充，允许是带结构的线性表的是( )。
【电子科技大学 2001 一、8(1 分) 】（A）串（B）树（C）广义表（D）栈4 下面说法不正确的是( )。
【南京理工大学 2001 一、3(15 分)】【江苏大学2006 一、1(2 分) 】（A）广义表的表头总是一个广义表（B）广义表的表尾总是一个广义表（C）广义表难以用顺序存储结构（D）广义表可以是一个多层次的结构5 下面说法不正确的是( )。
【电子科技大学 2008 一、5(1 分)】（A）广义表的表尾总是一个广义表（B）广义表难以用顺序存储结构（C）广义表的表头总是一个广义表（D）广义表可以上是一个递归结构二、填空题6 设有一个。

14、三(10 分)】(1)CAR(CDR(a，b)，(c，d，(e ，f)(2)CDR(CAR(a，6b)，(c，d，(e ，f)(3)CAR(CDR(CAR(a， b)，(e，f)(4)CDR(CAR(CDR(a，b)，(e，f)(5)CDR(CDR(CAR(a，b)，(e，f)注：CAR 运算相当于有些教材中的 Head 运算，CDR 运算相当于 Tail 运算。
5 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。
(a ， (0，b)，(e)【清华大学 1995 二(10 分)】6 画出下列广义表的两种存储结构图(0，A，B，(C ，D) ，(E,F)。
【南京航空航天大学 1999 三(10 分) 】7 知广义表 A=(a)，(b)，c，(a) ，(d,e)(1)画出其一种存储结构图；(2)写出表的长度与深度；(3)用求头部、尾部的方式求出 e。
【东北大学 1997 一、2(5 分)】8 画出具有共享结构广义表(b，c) ，d，(a) ，(a)， (b，c) ，d)，e，0)的存储表示。

15、以列序为主序顺序存储，基地址为 1024，每个元素占 2 个存储单元，第 4 行第 5 列的元素(假定无第 0 行第 0 列)的存储地址是( )。
【华中科技大学 2006 一、3(2 分)】（A）1068（B） 1086（C） 1084 （D）10663 若 6 行 5 列的数组以列序为主序顺序存储，基地址为 1000，每个元素占 2 个存储单元，则第 3 行第 4 列的元素(假定无第 0 行第 0 列)的地址是( )。
【华中科技大学 2004 一、4(1 分) 】（A）1040（B） 1042（C） 1026 （D）备选答案 A，B，C 都不对3 二维数组 A 的元素都是 6 个字符组成的串，行下标 i 的范围从 0 到 8，列下标 j的范围从 1 到 从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。
(1)存放 A 至少需要 ( )个字节；(2)A 的第 8 N 一和第 5 行共占( ) 个字节；(3)若 A 按行存放，元素 A8，5 的起始地址与 A 按列存放时的元素( )的起始地址一致。
【山东工业大学 2000 三、1(4 分)】【山东大学 1。

16、表示取广义表的头部)。
【中国科学技术大学 1995 十四、5(2 分)】（分数：2.00）A.a，6，b，aB.b，a，a，bC.a，a，b，bD.b，a，a，b E：a，b，b，a Fb，b，a，a2.广义表()的表头是( )，表尾是( )。
【电子科技大学 2003 一、4(208 分)】（分数：2.00）A.OB.NILC.(O)D.(O)3.将线性表的数据元素进行扩充，允许是带结构的线性表的是( )。
【电子科技大学 2001 一、8(1 分)】（分数：2.00）A.串B.树C.广义表D.栈4.下面说法不正确的是( )。
【南京理工大学 2001 一、3(15 分)】【江苏大学 2006 一、1(2 分)】（分数：2.00）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构5.下面说法不正确的是( )。
【电子科技大学 2008 一、5(1 分)】（分数：2.00）A.广义表的表尾总是一个广义表B.广义表难以用顺序存储。

17、2.数组 A 中，每个元素 Ai，f的长度均为 32 个二进位，行下标从一 1 到 9，列下标从 1 到 11，从首地址 S 开始连续存放在主存储器中，主存储器字长为 16 位。
求：(1)存放该数组所需多少单元?(2)存放数组第 4 列所有元素至少需多少单元?(3)数组按行存放时，元素 A7，4的起始地址是多少?(4)数组按列存放时，元素 A4，7的起始地址是多少?【大连海事大学 1996 四、1(6 分)】（分数：2.00）_3.假设按低下标优先存储整型数组 A(一 3：8，3：5，一 4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占 4 字节，问 A(0，4，一 2，5)的存储地址是什么? 【清华大学 1996 三】（分数：2。

18、元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是( )。
【南京理工大学 1999 二、8(2 分)】（分数：2.00）A.60B.66C.18000D.333.数组 A04，一 1-3，57中含有元素的个数( )。
【中山大学 1998 二、5(2 分)】（分数：2.00）A.55B.45C.36D.164.用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 j 沿链移动的操作为( )。
【南京理工大学 2001 一、1 6(15 分)】（分数：2.00）A.j=rfnextB.j=1+1C.j=f 一nextD.j=rj一next5.一个非空广义表的表尾( )。
【北京交通大学 2004 一、2(2 分)】（分数：2.00）A.不能是子表B.只能是子表C.只能是原子D.是原子或子表6.广义表(a)，(b，(c)，(e(e，f)，o)的深度是( )。
【华中科技大学 2007 一、7(2 分)】（分数：2.00）A.2B.3C.4D.57.广义表(a，(b，(c，d(e，f)，g)。

19、B.1 180C.1205D.12102.设 7 行 6 列的数组 a 以列序为主序顺序存储，基地址为 1024，每个元素占 2 个存储单元，第 4 行第 5列的元素(假定无第 0 行第 0 列)的存储地址是( )。
【华中科技大学 2006 一、3(2 分)】（分数：2.00）A.1068B.1086C.1084D.10663.若 6 行 5 列的数组以列序为主序顺序存储，基地址为 1000，每个元素占 2 个存储单元，则第 3 行第 4列的元素(假定无第 0 行第 0 列)的地址是( )。
【华中科技大学 2004 一、4(1 分)】（分数：2.00）A.1040B.1042C.1026D.备选答案 A，B，C 都不对二维数组 A 的元素都是 6 个字符组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范围从 1 到 从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。
(1)存放 A 至少需要( )个字节；(2)A的第 8 N 一和第 5 行共占( )个字节；(3)若 A 按行存放，元素 A8，5的起始地址与 A 按列存放时的元素( )的起始地址一致。

20、2.数组、广义表与线性表之间有什么样的关系?【西北工业大学 1998 一、2(4 分)】（分数：2.00）_3.什么是广义表?请简述广义表和线性表的主要区别。
【北京大学 1997 二、2(5 分)】（分数：2.00）_4.求下列广义表的运算结果。
【南京航空航天大学 1998 三(10 分)】(1)CAR(CDR(a，b)，(c，d，(e，f)(2)CDR(CAR(a，6b)，(c，d，(e，f)(3)CAR(CDR(CAR(a，b)，(e，f)(4)CDR(CAR(CDR(a，b)，(e，f)(5)CDR(CDR(CAR(a，b)，(e，f)注：CAR 运。