1.串是一种特殊的线性表，其特殊性体现在（ ）
A:数据元素可以是多个字符
B:数据元素是单个字符
C:可以是顺序存储
D:可以链接存储
答案:AI参考:正确答案是B:数据元素是单个字符。\n\n串是一种特殊的线性表，其特殊性体现在数据元素是单个字符。串中的字符可以是任意类型的数据，可以是整数、浮点数、字符串等，但每个元素必须是单个字符。串的存储方式可以是顺序存储或链式存储，但这并不是其特殊性所在。因此，选项B是正确答案。'
2.在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行
A:.q->next=p；p->next=q
B:q->next=p->next；p->next=q；
C:q->next=p->next；p=q；
D:p->next=q；q->next=p；
答案:AI参考:在非空线性链表中由p所指结点的后面插入一个由q所指的结点，正确的操作应该是：D:p->next=q；q->next=p；这是因为，首先将p的下一个节点指向q，然后再将q的下一个节点指向p，这样就完成了在p后面插入q的操作。选项A和B都是错误的，因为它们没有正确地处理p和q的链接关系。选项C也是错误的，因为它在插入q后，将p重新指向q，这会导致p链表出现环路。因此，正确答案是D：p->next=q；q->next=p。'
3.线性表采用链式存储结构时，要求内存中可用存储单元的地址( )
A:连续和不连续都可以
B:一定是不连续的
C:必须是部分连续的
D:必须是连续的
答案:AI参考:在内存中，线性表采用链式存储结构时，要求内存中可用存储单元的地址必须是连续的。这是因为链式存储结构需要使用链表指针来链接各个元素，这就要求内存中的地址必须是连续的，以便于分配和管理。其他选项都不符合链式存储结构的特性。因此，正确答案是D:必须是连续的。'
4.在双向链表存储结构中，删除p所指结点时须修改指针（ ）
A:p->next=p->next->next;p->next->prior=p;
B:p->prior=p->next->next;p->next=p-->prior->prior;
C:p->prior->next=p;p->prior=p->prior->prior;
D:p->next->prior=p->prior;p->prior->next=p->next;
答案:AI参考:在双向链表存储结构中，删除p所指结点时，需要修改指针的选项是C：p->prior->next=p;p->prior=p->prior->prior;\n\n解释：双向链表中的每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。当我们删除一个节点时，需要更新前一个节点和后一个节点的指针。所以选项C中，将p的后一个节点的指针指向前一个节点（即p的前一个节点），然后将p的前一个节点的指针指向p，从而完成了节点的删除。选项A、B、D都没有正确完成删除操作。'
5.已知数组 A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为（ ）。
A:1341
B:1340
C:1339
D:1342
答案:1340
6.线性表是具有n个（ ）的有限序列
A:数据元素
B:字符
C:关系
D:数据项
答案:数据元素
7.串的长度是指（ ）。
A:串中所含不同字母的个数
B:串中所含字符的个数
C:串中所含不同字符的个数
D:串中所含非空格字符的个数
答案:串中所含不同字母的个数
8.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。
A:40,50,20,95
B:45,40,15,20
C:15,20,40,45
D:15,40,60,20
答案:15,40,60,20
9.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）
A:23
B:44
C:37
D:46
答案:44
10.设循环队列的存储空间为a[0…20]，且当前队头指针和队尾指针的值分别为8和3，则该队列中的元素个数为（ ）
A:5
B:6
C:17
D:16
答案:16
11.以下排序方法中，（ ）不需要进行关键字的比较。
A:快速排序
B:堆排序
C:归并排序
D:基数排序
A:双向链表 B:单向链表 C:单向循环链表 D:双向循环链表 13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点。
A:99 B:101 C:102 D:100 14.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍
A:1 B:2 C:0.5 D:4 15.对于一个具有 n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为（ ）,在给定值为x的结点后插入一个新结点的时间复杂度为（ )。
A:O(n2)，O(e) B:O(1)，O(e) C:O(n2)，O(n+e) D:O(1),O(n) 16.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。
A:9，5,2,3 B:1，2,3 C:9，4,2,3 D:9，5,3 17.G是一个非连通无向图，共有28条边，则该图至少有 ( ）个顶点。
A:8 B:9 C:7 D:6 18.三元组用来存储（ ）
A:广义表 B:特殊矩阵 C:稀疏矩阵 D:稠密矩阵 19.某线性表中最常用的操作是读取序号为i的元素和在最后进行插入删除运算，则采用（ ）存储方式时间性能最好。
A:单向循环链表 B:双向链表 C:顺序表 D:双向循环链表 20.非空循环单链表head的尾结点p满足（ ）
A:p.next==head B:p==head C:p==null D:p.next==null 21.一组记录的排列码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（ ）
A:84,79,56,38,40,46 B:79,46,56,38,40,84 C:84,79,56,46,40,38 D:84,56,79,40,46,38 22.树的先根序列等同于与该树对应的二叉树的（ ）
A:后序序列 B:中序序列 C:层序序列 D:先序序列 23.一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF,则后序遍历序列为（ ）
A:不确定 B:CBEDFA C:FEDCBA D:CBEFDA 24.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。
A:5 B:8 C:3 D:4 25.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为
A:3，2，5，4，1，6 B:1，4，6，5，2，3 C:5，4，3，2，1，6 D:2，3，5，6，1，4 26.深度为k的完全二叉树中最少有（ ）个结点。
A:2k-1-1 B:2k-1 C:2k-1 D:2k-1 27.以下关于线性表的叙述，正确的是（ ）
A:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个前驱和后继元素 B:每个元素都有一个前驱和后继元素 C:线性表中至少有一个元素 D:线性表中元素的排列次序必须是由小到大或由大到小 28.广义表运算： tail ((( a, b ), ( c , ( d, e )))) =（ ）。
A:c,(d,e) B:(d,e) C:((c,(d,e))) D:(c,(d,e)) 29.一棵二叉排序树是由关键字集合{18，43，27，44，36，39}构建的，其中序遍历序列是（ ）
A:44，43，39，36，27，18 B:18，43，27，44，36，39 C:18，27，36，39，43，44 D:树形未定，无法确定 30.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。
A:N0=2N1+l B:N0=Nl+N2 C:N0=N1+1 D:N0=N2+1 31.二路归并排序的时间复杂度为（ ）。
A:O(n) B:O(n2) C: O(1og2n) D:O(nlog2n) 32.栈和队列的共同点是（ ）
A:没有共同点 B:都是后进后出 C:只允许在端点处插入和删除元素 D:都是先进先出 33.对稀疏矩阵进行压缩存储的目的是（ ）
A:降低运算的时间复杂度 B:便于输入和输出 C:便于进行矩阵运算 D:节省存储空间 34.一个栈的进栈序列是a,b,e.d,e,则栈的不可能的输出序列是（ ）
A:abcde B:decba C:dceab D:edcba 35.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。
A:15，25，35，50，80，20，85，40，70，85 B:15，25，35，50，80，20，36，40，70，85 C:15，25，35，50，20，40，80，85，36，70 D:15，25，35，50，80，20，85，40，70，36 36.一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比，会失去（ ）
A:随机存取 B:以上都不对 C:顺序存储 D:输入/输出 37.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ ）
A:ABCDEF B:FEDCBA C:FDECBA D:FBDCEA 38.设有向图G中的有向边的集合E={，，，，，，}，则该图的一个拓扑序列为( ）
A:124635 B:123456 C:124653 D:146532 39.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）。
A:匹配 B:联接 C:求串长 D:求子串 40.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（ ）。
A:head==0 B:head->next==0 C:head->next==head D:head!=0 41.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )
A:单链表 B:用头指针表示的单循环链表 C:顺序表 D:用尾指针表示的单循环链表 42.在含有27个结点的二叉排序树上查找关键字为35的结点，则依次比较的关键字有可能是（ ）
A:46，28，18，36，35 B:46，36，18，28，35 C:28，36，18，46，35 D:18，36，28，46，35 43.以下关于链式存储结构的描述中，（ ）是不正确的。
A:结点除自身信息外还包括指针域，因此存储密度不是很大。 B:结点除自身信息外还包括指针域，因此存储密度不是很大 C:可以通过计算直接确定第i个结点的地址。 D:插入删除方便，不必移动结点。 44.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（ ）
A:SXSSXXXX B:SSSXXSXX C:SXXSXSSX D:SXSXXSSX 45.下列叙述中不符合m阶B树定义要求的是（ ）
A:各结点内关键字均升序或降序排列 B:根结点最多有m个子树 C:所有叶结点都在同一层上 D:叶结点之间通过指针链接 46.对线性表进行二分查找时，要求线性表必须是（ ）
A:以链式方式存储 B:以顺序方式存储，且结点按关键字有序排列 C:以链式方式存储，其结点按关键字有序排列 D:以顺序表存储 47.广义表(a,(a,b),d,e,((i,j),k))的长度是（ ），深度是（ ）。
A:6，3 B:5，2 C:6，2 D:5，3 48.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。
A:40 B:45 C:20 D:30 49.稀疏矩阵的压缩存储一般采用（ ）存储方式。
A:三元组表 B:二元组表 C:数组 D:链表 50.关键路径是事件结点网络中（ ）
A:最长的回路 B:从源点到汇点的最短路径 C:从源点到汇点的最长路径 D:最短的回路 51.已知在顺序表中每个元素需占用8个存储单元，且LOC（a1）=100,则LOC（a5）=( )
A:132 B:148 C:150 D:140 52.元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（ ）
A:B，C，D，E，A B:E，A，B，C，D C:E，D，C，B，A D:A，B，C，D，E 53.在栈中进行插入和删除操作的一端称为（ ）
A:指定位置 B:栈顶 C:栈底 D:任意位置 54.下列四种排序中（ ）的空间复杂度最大。
A:堆 B:快速排序 C:希尔排序 D:冒泡排序 55.逻辑上通常可以将数据结构分为
A:顺序结构和链式结构 B:线性结构和非线性结构 C:初等结构和组合结构 D:动态结构和静态结构 56.数据结构中评价算法的两个重要指标是时间复杂度、空间复杂度。
A:错 B:对 57.在 n个结点的无向图中，若边数大于n-1,则该图必存在环路。
A:错 B:对 58.一个字符串中任意个连续字符成为该串的子串。
A:对 B:错 59.链式存储的特点是利用指针来表示数据元素之间的逻辑关系。
A:对 B:错 60.空格穿的长度为串中空格的个数。
A:对 B:错
