数据结构第一次作业题及答案

《数据结构第一次作业题及答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1次作业一、单项选择题（本大题共60分，共20小题，每小题3分）1.在长度为n的顺序表求最小值的时间复杂度为（）。A.O（1）B.O（n）C.O（n2）D.O（logn）2.顺序表中数据元素的存取方式是（）。A.顺序存取B.链式存取C.随机存取D.散列存取3.对于一个具有n个结点的单链表，,在给定值为x的结点后插入一个新结点的平均时间复杂度为（）。A.O(0)B.O(1)C.O(n)D.O(n2)4.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。A.行号B.列号C.元素值D.地址5.数组A［0..5］［0..5］的每个元素占

2、5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（　　　）。A.1175B.1180C.1205D.12106.下面程序段的时间复杂度是（）。i＝0；while（i<=n）i=i*3；A.O（3n）B.O(log3n)C.O(n3)D.O(n2)7.假设顺序表中第一个数据元素的存储地址是1000，每个元素占用4个字节，则第7个元素的存储地址是（）。A.1028B.1024C.1004D.10078.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素

3、出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是()。A.6B.4C.3D.29.判断带头结点的循环单链表L中只有一个结点的条件是（）。A.L==NULLB.L->next==LC.L->next->next==LD.L->next==NULL10.下面关于算法说法错误的是（）。A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的11.用单链表表示的链队列中，队头在链表的（）位置。A.链头B.链尾C.链中D.以上都不对12.世界上第一台电子计算机

4、问世的时间是（）。A.1946B.1920C.1948D.195013.如果对含有n（n>1）个元素的线性表运算只有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素后面插入新元素，则最好使用（）。A.只有尾结点指针没有头结点指针的循环单链表B.只有尾结点指针没有头结点指针的非循环双链表C.只有头结点指针没有尾结点指针的循环双链表D.既有头结点指针也有尾头结点指针的循环单链表14.（）描述算法最容易出现二义性。A.自然语言B.程序设计语言C.伪代码D.流程图15.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第

5、i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i16.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。A.10B.19C.28D.5517.在括号匹配的检验中，用（）作为转换过程中的数据存储结构。A.线性表B.栈C.队列D.单链表18.数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（）。A.r－f;B.（

6、n＋f－r）%n;C.n＋r－f;D.（n＋r－f）%n19.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以20.某字符串满足：concat(head(s),head(tail(tail(s))))=“ac”,(head,tail的定义同广义表),则S=()。A.aabcB.acbaC.acccD.acac二、判断题（本大题共40分，共20小题，每小题2分）1.线性结构中，每一个结点都至少有一个直接前驱和一个直接后继。2.数组是同类型值的集合。3.数组不适合作为

7、任何二叉树的存储结构。4.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。5.二维数组和多维数组均不是特殊的线性结构。6.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应等于对应三元组线性表的长度。7.已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p=p->next。8.栈不能用链式存储结构存放。9.在广义表的存储结构中，每个结点均包含有3个域。10.从逻辑结构上看，n维数组的每个元素均属于n个向量。11.带头结点的双循环链表L为空表的条件是：L->next==L。12.在顺序表中插入或删除一个元素，平均需要移

8、动大量的元素，具体移动的元素个数仅与该元素在表中的位置有关。13.