超星尔雅数据结构与算法答案

数据结构与算法尔雅答案

1.7引论
1【单选题】在数据结构中,从逻辑上可以把数据结构分成(C)。
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
2【单选题】在数据结构中,从存储结构上可以将之分为(B)。
A、动态结构和静态结构
B、顺序存储和非顺序存储
C、紧凑结构和非紧凑结构
D、线性结构和非线性结构
3【单选题】某算法的时间复杂度是O(n^2),表明该算法的(A)。
A、执行时间与n^2成正比
B、问题规模是n^2
C、执行时间等于n^2
D、问题规模与n^2成正比
4【单选题】在下面的程序段中,x=x+1;的语句频度为(D)。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;
A、O(2n)
B、O(n)
C、O(n^2)
D、O(log2n)
5【单选题】以下数据结构中,(A)是非线性数据结构。
A、树
B、字符串
C、队
D、栈
6【单选题】顺序存储,存储单元的地址(A)。
A、一定连续
B、一定不连续
C、不一定连续
D、部分连续,部分不连续
7【单选题】评价一个算法性能好坏的重要标准是(C)。
A、算法的正确性
B、算法易于调试
C、算法的时间和空间复杂度
D、算法易于理解
8【单选题】若需要利用形式参数直接访问修改实参值,则应将形参说明为(C)参数。
A、值参数
B、实地址
C、指针
D、地址参数
9【多选题】在数据结构中,从逻辑上可以把数据结构分成(AB)。
A、线性结构
B、树型结构
C、图状结构
D、集合
10【多选题】在数据结构中,从存储结构上可以将之分为(AB)。
A、顺序结构
B、非顺序结构
C、紧凑结构和非紧凑结构
D、线性结构和非线性结构
11【多选题】算法必须具备(BCD)这三个特性。
A、可扩充性
B、可执行性
C、确定性
D、有穷性
12【判断题】顺序存储方式的优点是存储密度大,且插入、删除运算效率高。X
13【判断题】数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。√
14【判断题】算法可以用不同的语言描述,如果用C语言或PASCAL语言等高级语言来描述,则算法实际上就是程序了。X
15【判断题】程序一定是算法。X
16【判断题】一个数据结构在计算机中的表示(又称映像)称为存储结构。√
2.7线性表
1【单选题】下述哪一条是顺序存储结构的优点(D)。
A、可方便地用于各种逻辑结构的存储表示
B、插入运算方便
C、删除运算方便
D、存储密度大
2【单选题】若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。
A、顺序表
B、双链表
C、带头结点的双循环链表
D、单循环链表
3【单选题】设某顺序表中第一个元素的地址是se(下标从1开始),每个结点占m个单元,则第i个结点的地址为(A)。
A、se+(i-1)×m
B、se+(i+1)×m
C、se+i×m
D、se-i×m
4【单选题】某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(B)存储方式最节省运算时间。
A、单链表
B、仅有尾指针的单循环链表
C、仅有头指针的单循环链表
D、双链表
5【单选题】若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为(A)。
A、O(n)
B、O(0)
C、O(1)
D、O(n^2)
6【单选题】在单链表指针为p的结点之后插入指针为s的结点,正确的操作是(B)。
A、s->next=p->next;p->next=s;
B、p->next=s;s->next=p->next;
C、p->next=s;p->next=s->next;
D、p->next=s->next;p->next=s;
7【单选题】对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是(A)。
A、head→next==NULL;
B、head==NULL;
C、head→next==he;
D、head!=NULL;
8【判断题】静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。√
9【判断题】顺序表适宜于顺序存取,而链表适宜于随机存取。X
10【判断题】线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。√
11【判断题】链表的性能优于顺序表。X
12【判断题】线性表的特点是每个元素都有一个前驱和一个后继。X
3.9栈和队列
1【单选题】栈和队列都是(D)。
A、限制存取点的非线性结构
B、顺序存储的线性结构
C、链式存储的非线性结构
D、限制存取点的线性结构
2【单选题】设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后随即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是(A)。
A、3
B、6
C、4
D、2
3【单选题】设计一个判别表达式中括号是否匹配出现的算法,采用(A)的数据结构最佳。
A、栈
B、顺序表
C、队列
D、单链表
4【单选题】表达式a*(b+c)-d的后缀表达式是(C)。
A、abc*+d-
B、cb+a*d-
C、abc+*d-
D、abcd+*-
5【单选题】递归过程或函数调用时,处理参数及返回地址需要用一种(A)的数据结构。
A、栈
B、队列
C、多维数组
D、线性表
6【单选题】最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是(A)。
A、rear==front
B、(rear+1)%n==front
C、rear+1==front
D、(rear-l)%n==front
7【单选题】用带头结点的单链表表示队长大于1的队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时(A)。
A、仅修改队头指针
B、仅修改队尾指针
C、队头、队尾指针都要修改
D、队头,队尾指针都可能要修改
8【单选题】对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为(A)。
A、O(1),O(n)
B、O(n),O(n)
C、O(1),O(1)
D、O(n),O(1)
9【判断题】两顺序栈共享空间,也存在空间溢出问题。√
10【判断题】在对不带头结点的链队列作出队操作时,不会改变头指针的值。X
11【判断题】消除递归不一定需要使用栈。√
12【判断题】顺序栈因为是顺序存储,所以可以随机存取栈中任意元素。X
13【判断题】任何一个递归过程都可以转换成非递归过程。√
14【判断题】栈和队列都是限制存取点的线性结构。√
4.7串
1【单选题】串是一种特殊的线性表,其特殊性体现在(A)。
A、数据元素是字符
B、顺序存储
C、链式存储
D、逻辑结构是线性结构
2【单选题】若串S='software',其前缀真子串的数目是(A)。
A、7
B、10
C、9
D、8
3【单选题】设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为(A)。
A、串的模式匹配
B、求子串
C、串联接
D、求串长
4【单选题】已知串S=‘aaab',其next函数值为(A)。
A、0123
B、1123
C、1231
D、1211
5【单选题】函数strcmp('stcabuc','stbabuc')的返回值是(D)。
A、0
B、-1
C、2
D、1
6【判断题】KMP算法的特点是在模式匹配时指示主串的指针不会回溯。√
7【判断题】模式串P=‘abaabcac'的next函数值序列为01122312。√
8【判断题】串的存储结构有顺序串、堆串和块链串三种。√
9【判断题】子串的定位运算称为串的模式匹配。√
10【判断题】串'student'和'Student'相等。X
11【判断题】如果两个串含有相同的字符,则说明它们相等。X
12【判断题】如果一个串中所有的字母均在另一个串中出现,则说明前者是后者的子串。X
5.5多维数组和广义表
1【单选题】假设以行序为主序存储二维数组A=array[1...100,1...100],设每个数组元素占2个存储单元,基地址为10,则LOC[5,5]=(A)。
A、818
B、B808
C、1010
D、1020
2【单选题】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1...(n(n+1))/2]中,则在B中确定aij(i B
A、j(j-1)/2+i
B、i(i-1)/2+j
C、i(i+1)/2+j
D、j(j+1)/2+i
3【单选题】
设广义表L=((a,b,c)),则L的长度和深度分别为(A)。
A、1和2
B、1和1
C、1和3
D、2和3
4【单选题】在稀疏矩阵的三元组顺序表中