2021年数据结构C语言版期末题库.doc

“数据构造”期末考试试题
一、单选题(每小题2分，共12分)
1．在一种单链表HL中，若要向表头插入一种由指针p指向结点，则执行( )。
A． HL＝ps p一>next＝HL
B． p一>next＝HL；HL＝p3
C． 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．48
C． 72 D． 53
5．当一种作为实际传递对象占用存储空间较大并也许需要修改时，应最佳把它阐明为
( )参数，以节约参数值传播时间和存储参数空间。
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．在一棵高度为h3叉树中，最多具有——结点。
5．假定一棵二叉树结点数为18，则它最小深度为——，最大深度为——·
6．在一棵二叉搜索树中，每个分支结点左子树上所有结点值一定——该结点值，右子
树上所有结点值一定——该结点值。
7．当向一种小根堆插入一种具备最小值元素时，该元素需要逐级——调节，直到被调节到
——位置为止。
8．表达图三种存储构造为——、——和———。
9．对用邻接矩阵表达具备n个顶点和e条边图进行任一种遍历时，其时间复杂度为——，
对用邻接表表达图进行任一种遍历时，其时间复杂度为——。
10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长
度分别为——和——·
11．假定对长度n＝144线性表进行索引顺序查找，并假定每个子表长度均为，则进
行索引顺序查找平均查找长度为——，时间复杂度为——·
12．一棵B—树中所有叶子结点均处在——上。
13．每次从无序表中顺序取出一种元素，把这插入到有序表中恰当位置，此种排序办法叫
做——排序；每次从无序表中挑选出一种最小或最大元素，把它互换到有序表一端，此种排序办法叫做——排序。
14．迅速排序在乎均状况下时间复杂度为——，最坏状况下时间复杂度为——。
三、运算题(每小题6分，共24分)
1．假定一棵二叉树广义表表达为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历成果。
先序：
中序；
后序：
2．已知一种带权图顶点集V和边集G分别为：
V＝{0，1，2，3，4，5}；
E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}， 则求出该图最小生成树权。
最小生成树权；
3．假定一组记录排序码为(46，79，56，38，40，84，50，42)，则运用堆排序办法建立
初始堆为——。
4．有7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵
哈夫曼树，求出该树带权途径长度、高度、双分支结点数。
带权途径长度：—— 高度：—— 双分支结点数：——。
四、阅读算法，回答问题(每小题8分，共16分)
1．VOldAC(List&L)
{
InitList(L)；
InsertRear(L;25)；
InsertFront(L，50)；
IntaL4]＝{5，8，12，15，36};
for(inti＝0；i<5；i++)
if (a[i]％2＝＝0)InsertFront(L，a[i])；
elselnsertRear(L，a[i])；
}
该算法被调用执行后，得到线性表L为：
2．void AG(Queue&Q)
{
InitQueue(Q)；
inta[5]＝{6，12，5，15，8}；
for(int i＝0;i<5；i++)QInsert(Q，a[i])；
QInsert(Q，QDelete(Q))；
QInsert(Q，20)；
QInsert(Q，QDelete(Q)十16)；
while(!QueueEmpty(Q))cout<<QDelete(Q)<<”；
}
该算法被调用后得到输出成果为：
五、算法填空，在画有横线地方填写适当内容(每小题6分，共12分)
1．从一维数组A[n)中二分查找核心字为K元素递归算法，若查找成功则返回相应元素
下标，否则返回一1。
IntBinsch(ElemTypeA[]，Intlow，int high，KeyTypeK)
{
if(low<＝high)
{
int mid＝(low+high)／2；
if(K＝＝A[mid].key)——；
else if (K<A[mid].key)——；
else ；
}
else return—l；
}
2．已知二叉树中结点类型BinTreeNode定义为：
structBinTreeNode{ElemType data；BinTreeNode*left，*right}；
其中data为结点值域，left和right分别为指向左、右子女结点指针域。下面函数功
能是返回二叉树BT中值为x结点所在层号，请在划有横线地方填写适当内容。 Int NodeLevel(BinTreeNode * BT，ElemType X)
{
if(BT：＝NULL)return 0； ／／空树层号为0
else if(BT一>data＝＝X)return 1；／／根结点层号为1
／／向子树中查找x结点
else{
int cl＝NodeLevel(BT一>left，X)；
if(cl>＝1)return cl+1;
int c2＝ ；
if——；
／／若树中不存在X结点则返回o
else return 0；
}
}
六、编写算法(8分)
按所给函数声明编写一种算法，从表头指针为HL单链表中查找出具备最大值结点，该最
大值由函数返回，若单链表为空则中断运营。
EIemType MaxValue(LNOde*HL);
“数据构造”期末考试试题答案
一、单选题(每小题2分，共12分)
评分原则；选对者得2分，否则不得分。
1．B 2．B 3．C 4．D 5．B 6．A
二、填空题(每空1分，共28分)
1．顺序构造 链接构造 索引构造 散列构造(顺序无先后)
2．值(或data) 子表指针(或sublist)
3．3 x 2．4 5／6一*十
4．(3h一1)／2
5． 5 18
6．不大于 不不大于(或不不大于等于)
7．向上 堆顶
8．邻接矩阵 邻接表 边集数组(顺序无先后)
9．O(n2) O(e)
10． 1 3
11．13 O()
12．同一层
13．插人 选取
14．O(nlog2n) O(n2)
三、运算题(每小题6分，共24分)
1．先序：a，b，c，d，e，f，e ／／2分
中序：c，b，d，a，f，8，e ／／2分
后序：c，d，b，e，f，e，a ／／2分
2．最小生成树权：31 ／／6分
3．(84，79，56，42，40，46，50，38) ／／6分
4．带权途径长度：131 ／／3分
高度：5 ／／2分
双分支结点数：6 ／／1分
四、阅读算法，回答问题(每小题8分，共16分)
评分原则：每小题对的得8分，浮现一处错误扣4分，两处及以上错误不得分。
1．(36，12，8，50，25，5，15)
2．5 15 8 6 20 28
五、算法填空，在画有横线地方填写适当内容(每小题6分，共12分)
1．feturn mid ／／2分
returnBinsch(A，low，mid一1，K) ／／2分
returnBmsch(A，mid+1，high，K) ／／2分
2．NodeLevel(BT一>right，X) ／／3分
(c2>=1)returnc2十1 ／／3分
六、编写算法(8分)
评分原则：请参照语句后注释，或依照状况酌情给分。
ElemType MaxValue(LNodeO* HL。)
{
if (HL＝=NUlL){ ／／2分
cerr<<"Linked llst is empty!”<<endl；
exit(1)；
}
ElemTypemax：HL一>data； ／／3分
LNOde*p=HI一>next； ／／4分
while(P!：NULL){ ／／7分
if(max<p一>data)max＝p一>data；
p＝p一>next；
}
returnmax； ／／8分
}
数据构造复习资料
一、填空题
1. 数据构造是一门研究非数值计算程序设计问题中计算机 操作对象 以及它们之间 关系 和运算等学科。
2. 数据构造被形式地定义为（D，R），其中D是 数据元素 有限集合，R是D上 关系 有限集合。
3. 数据构造涉及数据 逻辑构造 、数据 存储构造 和数据 运算 这三个方面内容。
4. 数据构造按逻辑构造可分为两大类，它们分别是 线性构造 和 非线性构造 。
5. 线性构造中元素之间存在一对一关系，树形构造中元素之间存在一对多关系，图形构造中元素之间存在多对多关系。
6． 在线性构造中，第一种结点 没有 前驱结点，别的每个结点有且只有 1个前驱结点；最后一种结点 没有 后续结点，别的每个结点有且只有1个后续结点。
7. 在树形构造中，树根结点没有 前驱 结点，别的每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，别的每个结点后续结点数可以任意各种 。
8. 在图形构造中，每个结点前驱结点数和后续结点数可以 任意各种 。
9．数据存储构造可用四种基本存储办法表达，它们分别是顺序 、链式 、索引 和 散列 。
10. 数据运算最惯用有5种，它们分别是插入 、删除、修改、查找 、排序。
11. 一种算法效率可分为 时间 效率和 空间 效率。
12. 在顺序表中插入或删除一种元素，需要平均移动 表中一半元素，详细移动元素个数与 表长和该元素在表中位置 关于。
13. 线性表中结点集合是 有限 ，结点间关系是 一对一 。
14. 向一种长度为n向量第i个元素(1≤i≤n+1)之前插入一种元素时，需向后移动 n-i+1 个元素。
15. 向一种长度为n向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
16. 在顺序表中访问任意一结点时间复杂度均为 O(1) ，因而，顺序表也称为 随机存取 数据构造。
17. 顺序表中逻辑上相邻元素物理位置 必然相邻。单链表中逻辑上相邻元素物理位置 不一定 相邻。
18．在单链表中，除了首元结点外，任一结点存储位置由 其直接前驱结点链域值 批示。
19． 在n个结点单链表中要删除已知结点*p，需找到它前驱结点地址，其时间复杂度为O（n）。
20. 向量、栈和队列都是 线性 构造，可以在向量 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。
21. 栈是一种特殊线性表，容许插入和删除运算一端称为 栈顶 。不容许插入和删除运算一端称为 栈底 。
22. 队列 是被限定为只能在表一端进行插入运算，在表另一端进行删除运算线性表。
23. 不包括任何字符（长度为0）串 称为空串； 由一种或各种空格（仅由空格符）构成串 称为空白串。
24. 子串定位运算称为串模式匹配； 被匹配主串 称为目的串， 子串 称为模式。
25. 假设有二维数组A6×8，每个元素用相邻6个字节存储，存储器按字节编址。已知A起始
存储位置（基地址）为1000，则数组A体积（存储量）为 288 B ；末尾元素A57第一种字节地址为 1282 ；若按行存储时，元素A14第一种字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A47第一种字节地址为 (6×7＋4)×6＋1000）＝1276 。
26． 由３个结点所构成二叉树有 5 种形态。
27. 一棵深度为6满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。
注：满二叉树没有度为1结点，因此分支结点数就是二度结点数。
28． 一棵具备２５７个结点完全二叉树，它深度为 9 。
（ 注：用ë log2(n) û+1= ë 8.xx û+1=9
29．设一棵完全二叉树有700个结点，则共有 350 个叶子结点。
答：最快办法：用叶子数＝[n/2]＝350
30． 设一棵完全二叉树具备1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快办法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 此外，最后一结点为2i属于左叶子，右
叶子是空，因此有1个非空左子树。完全二叉树特点决定不也许有左空右不空状况，因此
非空右子树数＝0.
31．在数据存储无规律而言线性表中进行检索最佳办法是 顺序查找（线性查找） 。
32. 线性有序表（a1，a2，a3，„，a256)是从小到大排列，对一种给定值k，用二分法检索表
中与k相等元素，在查找不成功状况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。
33. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功结点数为1；比较两次查找成功结点数为 2 ；比较四次查找成功结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O（log2n）<5次（25）。但详细是多少次，则不应当按照公式
ASL=n+1log2(n+1)来计算（即（21×log221）/20＝4.6n次并不对的！）。由于这是在假设n＝2m-1状况下推导出来公式。应当用穷举法罗列：
所有元素查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！
34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
35. 在各种查找办法中，平均查找长度与结点个数n无关查找办法是 散列查找 。
36. 散列法存储基本思想是由 核心字值 决定数据存储地址。
二、判断正误（在对的说法背面打勾，反之打叉）
（ × ）1. 链表每个结点中都正好包括一种指针。
答：错误。链表中结点可含各种指针域，分别存储各种指针。例如，双向链表中结点可以具有两个指针域，分别存储指向其直接前趋和直接后继结点指针。
（ × ）2. 链表物理存储构造具备同链表同样顺序。错，链表存储构造特点是无序，而链表达意图有序。
（ × ）3. 链表删除算法很简朴，由于当删除链中某个结点后，计算机会自动地将后续各个单元向前移动。错，链表结点不会移动，只是指针内容变化。
（ × ）4. 线性表每个结点只能是一种简朴类型，而链表每个结点可以是一种复杂类型。 错，混淆了逻辑构造与物理构造，链表也是线性表！且虽然是顺序表，也能存储记录型数据。 （ × ）5. 顺序表构造适当于进行顺序存取，而链表适当于进行随机存取。
错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”
（ × ）6. 顺序存储方式长处是存储密度大，且插入、删除运算效率高。
错，前一半对的，但后一半说法错误，那是链式存储长处。顺序存储方式插入、删除运算效率较低，在表长为n顺序表中，插入和删除一种数据元素，平均需移动表长一半个数数据元素。 （ × ）7. 线性表在物理存储空间中也一定是持续。
错，线性表有两种存储方式，顺序存储和链式存储。后者不规定持续存储。
（ × ）8. 线性表在顺序存储时，逻辑上相邻元素未必在存储物理位置顺序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻元素在存储物理位置顺序上也相邻。
（ × ）9. 顺序存储方式只能用于存储线性构造。
错误。顺序存储方式不但能用于存储线性构造，还可以用来存储非线性构造，例如完全二叉树是属于非线性构造，但其最佳存储方式是顺序存储方式。（后一节简介）
（ × ）10. 线性表逻辑顺序与存储顺序总是一致。
错，理由同7。链式存储就无需一致。
（ × ）11. 线性表每个结点只能是一种简朴类型，而链表每个结点可以是一种复杂类型。 错，线性表是逻辑构造概念，可以顺序存储或链式存储，与元素数据类型无关。
（ × ）12. 在表构造中最惯用是线性表，栈和队列不太惯用。
错，不一定吧？调用子程序或函数惯用，CPU中也用队列。
（ √ ）13. 栈是一种对所有插入、删除操作限于在表一端进行线性表，是一种后进先出型构造。
（ √ ）14. 对于不同使用者，一种表构造既可以是栈，也可以是队列，也可以是线性表。 对的，都是线性逻辑构造，栈和队列其实是特殊线性表，对运算定义略有不同而已。 （ × ）15. 栈和链表是两种不同数据构造。
错，栈是逻辑构造概念，是特殊殊线性表，而链表是存储构造概念，两者不是同类项。 （ × ）16. 栈和队列是一种非线性数据构造。
错，她们都是线性逻辑构造，栈和队列其实是特殊线性表，对运算定义略有不同而已。 （ √ ）17. 栈和队列存储方式既可是顺序方式，也可是链接方式。
（ √ ）18. 两个栈共享一片持续内存空间时，为提高内存运用率，减少溢出机会，应把两个栈栈底分别设在这片内存空间两端。
（ × ）19. 队是一种插入与删除操作分别在表两端进行线性表，是一种先进后出型构造。 错，后半句不对。
（ × ）20. 一种栈输入序列是12345，则栈输出序列不也许是12345。
错，有也许。
（ √ ）21. 若二叉树用二叉链表作存贮构造，则在n个结点二叉树链表中只有n—1个非空指针域。
（ × ）22.二叉树中每个结点两棵子树高度差等于1。
（ √ ）23.二叉树中每个结点两棵子树是有序。
（ × ）24.二叉树中每个结点有两棵非空子树或有两棵空子树。
（ × ）25.二叉树中每个结点核心字值不不大于其左非空子树（若存在话）所有结点核心字值，且不大于其右非空子树（若存在话）所有结点核心字值。 （应当是二叉排序树特点） （ × ）26.二叉树中所有结点个数是2k-1-1，其中k是树深度。（应2i-1）
（ × ）27.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（ × ）28.对于一棵非空二叉树，它根结点作为第一层，则它第i层上最多能有2i—1个结点。（应2i-1）
（ √ ）29.用二叉链表法（link-rlink）存储包括n个结点二叉树，结点2n个指针区域中有n+1个为空指针。
（ √ ）30.具备12个结点完全二叉树有5个度为2结点。
三、单项选取题
（ B ）1. 非线性构造是数据元素之间存在一种：
A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系
（ C ）2. 数据构造中，与所使用计算机无关是数据 构造；
A) 存储 B) 物理 C) 逻辑 D) 物理和存储
（ C ）3. 算法分析目是：
A) 找出数据构造合理性 B) 研究算法中输入和输出关系
C) 分析算法效率以求改进 D) 分析算法易懂性和文档性
（ A ）4. 算法分析两个重要方面是：
A) 空间复杂性和时间复杂性 B) 对的性和简要性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
（ C ）5. 计算机算法指是：
A) 计算办法 B) 排序办法 C) 解决问题有限运算序列 D) 调度办法
（ B ）6. 计算机算法必要具备输入、输出和 等5个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、拟定性和有穷性
C) 拟定性、有穷性和稳定性 D) 易读性、稳定性和安全性
（ C ）7．数据在计算机存储器内表达时，物理地址与逻辑地址相似并且是持续，称之为：
（A）存储构造 （B）逻辑构造 （C）顺序存储构造 （D）链式存储构造
（ B ）8.一种向量第一种元素存储地址是100，每个元素长度为2，则第5个元素地址是
（A）110 （B）108 （C）100 （D）120
（ A ）9. 在n个结点顺序表中，算法时间复杂度是O（1）操作是：
（A） 访问第i个结点（1≤i≤n）和求第i个结点直接前驱（2≤i≤n）
（B） 在第i个结点后插入一种新结点（1≤i≤n）
（C） 删除第i个结点（1≤i≤n）
（D） 将n个结点从小到大排序
（ B ）10. 向一种有127个元素顺序表中插入一种新元素并保持本来顺序不变，平均要移动 个元素
（A）8 （B）63.5 （C）63 （D）7
（ A ）11. 链接存储存储构造所占存储空间：
（A） 分两某些，一某些存储结点值，另一某些存储表达结点间关系指针
（B） 只有一某些，存储结点值
(C） 只有一某些，存储表达结点间关系指针
（D） 分两某些，一某些存储结点值，另一某些存储结点所占单元数
（ B ）12. 链表是一种采用 存储构造存储线性表；
（A）顺序 （B）链式 （C）星式 （D）网状
（ D ）13. 线性表若采用链式存储构造时，规定内存中可用存储单元地址:
（A）必要是持续 （B）某些地址必要是持续
（C）一定是不持续 （D）持续或不持续都可以
（ B ）14． 线性表Ｌ在 状况下合用于使用链式构造实现。
（Ａ）需经常修改Ｌ中结点值 （Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中具有大量结点 （Ｄ）Ｌ中结点构造复杂
（ B ）15.栈中元素进出原则是
Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出
（ C ）16. 若已知一种栈入栈序列是1，2，3，„，n，其输出序列为p1，p2，p3，„，pn，若p1=n，则pi为
Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不拟定
（ B ）17. 鉴定一种栈ST（最多元素为m0）为空条件是
Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0
（ C ）18. 在一种图中，所有顶点度数之和等于图边数 倍。
A．1/2 B. 1 C. 2 D. 4
（ B ）19. 在一种有向图中，所有顶点入度之和等于所有顶点出度之和 倍。
A．1/2 B. 1 C. 2 D. 4
（ B ）20. 有8个结点无向图最多有 条边。
A．14 B. 28 C. 56 D. 112 （ C ）21. 有8个结点有向完全图有 条边。
A．14 B. 28 C. 56 D. 112 （ B ）22．在表长为ｎ链表中进行线性查找，它平均查找长度为
Ａ. ＡＳＬ＝ｎ；Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝＋１；Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（ A ）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找成果是失败。
A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50
（ C ）24．对22个记录有序表作折半查找，当查找失败时，至少需要比较 次核心字。
A．3 B．4 C．5 D． 6
（ A ）25. 链表合用于 查找
A．顺序 B．二分法 C．顺序，也能二分法 D．随机
《数据构造与算法》复习题
一、选取题。
1．在数据构造中，从逻辑上可以把数据构造分为 C 。
A．动态构造和静态构造 B．紧凑构造和非紧凑构造
C．线性构造和非线性构造 D．内部构造和外部构造
2．数据构造在计算机内存中表达是指 A 。
A．数据存储构造 B．数据构造 C．数据逻辑构造 D．数据元素之间关系
3．在数据构造中，与所使用计算机无关是数据 A 构造。
A．逻辑 B．存储 C．逻辑和存储 D．物理
4．在存储数据时，普通不但要存储各数据元素值，并且还要存储 C 。
A．数据解决办法 B．数据元素类型
C．数据元素之间关系 D．数据存储办法
5．在决定选用何种存储构造时，普通不考虑 A 。
A．各结点值如何 B．结点个数多少
C．对数据有哪些运算 D．所用编程语言实现这种构造与否以便。
6．如下说法对的是 D 。
A．数据项是数据基本单位
B．数据元素是数据最小单位
C．数据构造是带构造数据项集合
D．某些表面上很不相似数据可以有相似逻辑构造
7．算法分析目是 C ，算法分析两个重要方面是 A 。
（1）A．找出数据构造合理性 B．研究算法中输入和输出关系
C．分析算法效率以求改进 C．分析算法易读性和文档性
（2）A．空间复杂度和时间复杂度 B．对的性和简要性
C．可读性和文档性 D．数据复杂性和程序复杂性
8．下面程序段时间复杂度是 O(n2) 。
s =0;
for( I =0；i<n；i++)
for(j=0;j<n;j++)
s +=B[i][j];
sum = s ;
9．下面程序段时间复杂度是 O(n*m) 。
for( i =0；i<n；i++)
for(j=0;j<m;j++)
A[i][j] ＝ 0;
10．下面程序段时间复杂度是 O(log3n) 。
i ＝ 0；
while（i<=n）
i = i * 3；
11．在如下论述中，对的是 B 。
A．线性表顺序存储构造优于链表存储构造
B．二维数组是其数据元素为线性表线性表
C．栈操作方式是先进先出
D．队列操作方式是先进后出
12．普通规定同一逻辑构造中所有数据元素具备相似特性，这意味着 B 。
A．数据元素具备同一特点
B．不但数据元素所包括数据项个数要相似，并且相应数据项类型要一致
C．每个数据元素都同样
D．数据元素所包括数据项个数要相等
13．链表不具备特点是 A 。
A．可随机访问任一结点 B．插入删除不需要移动元素
C．不必事先预计存储空间 D．所需空间与其长度成正比
14．不带头结点单链表head为空鉴定条件是 A 。
A．head == NULL B head->next ==NULL
C．head->next ==head D head!=NULL
15．带头结点单链表head为空鉴定条件是 B 。
A．head == NULL B head->next ==NULL
C．head->next ==head D head!=NULL
16．若某表最惯用操作是在最后一种结点之后插入一种结点或删除最后一种结点，则采用 D 存储方式最节约运算时间。
A．单链表 B．给出表头指针单循环链表 C．双链表 D．带头结点双循环链表
17．需要分派较大空间，插入和删除不需要移动元素线性表，其存储构造是 B 。
A．单链表 B．静态链表 C．线性链表 D．顺序存储构造
18．非空循环单链表head尾结点（由p所指向）满足 C 。
A．p->next == NULL B．p == NULL
C．p->next ==head D．p == head
19．在循环双链表p所指结点之前插入s所指结点操作是 D 。
A．p->prior = s；s->next = p；p->prior->next = s；s->prior = p->prior
B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior
C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
D．s->next = p；s->prior = p->prior；p->prior->next = s；p->prior = s
20．如果最惯用操作是取第i个结点及其前驱，则采用 D 存储方式最节约时间。
A．单链表 B．双链表 C．单循环链表 D． 顺序表
21．在一种具备n个结点有序单链表中插入一种新结点并依然保持有序时间复杂度是 B 。
A．O（1） B．O（n） C．O（n2） D．O（nlog2n）
22．在一种长度为n（n>1）单链表上，设有头和尾两个指针，执行 B 操作与链表长度关于。
A．删除单链表中第一种元素
B．删除单链表中最后一种元素
C．在单链表第一种元素前插入一种新元素
D．在单链表最后一种元素后插入一种新元素
23．与单链表相比，双链表长处之一是 D 。
A．插入、删除操作更简朴
B．可以进行随机访问
C．可以省略表头指针或表尾指针
D．顺序访问相邻结点更灵活
24．如果对线性表操作只有两种，即删除第一种元素，在最后一种元素背面插入新元素，则最佳使用 B 。
A．只有表头指针没有表尾指针循环单链表
B．只有表尾指针没有表头指针循环单链表
C．非循环双链表
D．循环双链表
25．在长度为n顺序表第i个位置上插入一种元素（1≤ i ≤n+1），元素移动次数为： A 。
A．n – i + 1 B．n – i C．i D．i – 1
26．对于只在表首、尾两端进行插入操作线性表，宜采用存储构造为 C 。
A．顺序表 B． 用头指针表达循环单链表
C．用尾指针表达循环单链表 D．单链表
27．下述哪一条是顺序存储构造长处？ C 。
A插入运算以便 B可以便地用于各种逻辑构造存储表达
C存储密度大 D删除运算以便
28．下面关于线性表论述中，错误是哪一种？ B 。
A线性表采用顺序存储，必要占用一片持续存储单元
B线性表采用顺序存储，便于进行插入和删除操作。
C线性表采用链式存储，不必占用一片持续存储单元
D线性表采用链式存储，便于进行插入和删除操作。
29．线性表是具备n个 B 有限序列。
A．字符 B．数据元素 C．数据项 D．表元素
30．在n个结点线性表数组实现中，算法时间复杂度是O（1）操作是 A 。
A．访问第i（1<=i<=n）个结点和求第i个结点直接前驱（1<i<=n）
B．在第i（1<=i<=n）个结点后插入一种新结点
C．删除第i（1<=i<=n）个结点
D．以上都不对
31．若长度为n线性表采用顺序存储构造，在其第i个位置插入一种新元素算法时间复杂度为 C 。
A．O(0) B．O(1) C．O(n) D．O(n2)
32．对于顺序存储线性表，访问结点和增长、删除结点时间复杂度为 C 。
A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)
33．线性表（a1,a2，„ ,an）以链式方式存储，访问第i位置元素时间复杂度为 C 。
A．O(0) B．O(1) C．O(n) D．O(n2)
34．单链表中，增长一种头结点目是为了 C 。
A．使单链表至少有一种结点 B．标记表结点中首结点位置
C．方面运算实现 D．阐明单链表是线性表链式存储
35．在单链表指针为p结点之后插入指针为s结点，对的操作是 B 。
A．p->next=s；s->next=p->next B． s->next=p->next ；p->next=s;
C．p->next=s；p->next=s->next D．p->next=s->next；p->next=s
36．线性表顺序存储构造是一种 A 。
A．随机存取存储构造 B．顺序存取存储构造
C．索引存取存储构造 D．Hash存取存储构造
37．栈特点是 B ，队列特点是 A 。
A．先进先出 B．先进后出
38．栈和队列共同点是 C 。
A．都是先进后出 B．都是先进先出
C．只容许在端点处插入和删除元素 D．没有共同点
39．一种栈进栈序列是a，b，c，d，e，则栈不也许输出序列是 C 。
A．edcba B．decba C．dceab D．abcde
40．设有一种栈，元素依次进栈顺序为A、B、C、D、E。下列 C 是不也许出栈序列。
A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A
41．如下 B 不是队列基本运算？
A．从队尾插入一种新元素 B．从队列中删除第i个元素
C．判断一种队列与否为空 D．读取队头元素值
42．若已知一种栈进栈序列是1，2，3，，n，其输出序列为p1，p2，p3，„，pn，若p1＝n，则pi为 C 。
A．i B．n－i C．n－i＋1 D．不拟定
43．鉴定一种顺序栈st（最多元素为MaxSize）为空条件是 B 。
A．st->top != -1 B．st->top == -1
C．st->top != MaxSize D． st->top == MaxSize
44．鉴定一种顺序栈st（最多元素为MaxSize）为满条件是 D 。
A．st->top != -1 B．st->top == -1
C．st->top != MaxSize D．st->top == MaxSize
45．一种队列入队序列是1，2，3，4，则队列输出序列是 B 。
A．4，3，2，1 B．1，2，3，4
C．1，4，3，2 D．3，2，4，1
46．鉴定一种循环队列qu（最多元素为MaxSize）为空条件是 C 。
A．qu->rear – qu->front ==MaxSize B．qu->rear – qu->front -1==MaxSize
C．qu->rear ==qu->front D． qu->rear =qu->front -1
47．在循环队列中，若front与rear 分别表达对头元素和队尾元素位置，则判断循环队列空
条件是 C 。
A．front==rear+1 B．rear==front+1 C．front==rear D．front==0
48．向一种栈顶指针为h带头结点链栈中插入指针s所指结点时，应执行 D 操作。
A．h->next=s ；B．s->next=h ;
C．s->next=h ;h =s ；D．s->next=h->next ;h->next=s ;
49．输入序列为ABC，可以变为CBA时，通过栈操作为 B 。
A．push，pop，push，pop，push，pop B．push，push，push，pop， pop， pop
C．push，push，pop， pop，push，pop D．push，pop，push，push，pop， pop
50．若栈采用顺序存储方式存储，现两栈共享空间V[1 m]，top[1]、top[2]分别代表第1和第2个栈栈顶，栈1底在V[1]，栈2底在V[m]，则栈满条件是 B 。
A．|top[2]-top[1]|=0 B． top[1]+1=top[2] C．top[1]+top[2]=m
D．top[1]=top[2]
51．设计一种鉴别表达式中左、右括号与否配对浮现算法，采用 D 数据构造最佳。
A．线性表顺序存储构