数据结构与算法（周测1-算法分析）
判断题
1.In a singly linked list of N nodes, the time complexities for query and insertion are O(1) and O(N), respectively.
T      F
查是O(N)，因为需要沿着next指针下去。⽽插⼊是O(1)，只需要改变指针就⾏了。
2.If N numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is O(logN).
T      F
因为链表不⽀持随机存取，⽽O(logN)的算法严重依赖于随机存取，所以不可能完成。
3.If keys are pushed onto a stack in the order abcde, then it's impossible to obtain the output sequence cedab.
F
a在b的前⾯意味着a如果不在⼀开始取出就不能在b之前被取出，所以是不可能的。
4.An algorithm to check for balancing symbols in an expression uses a queue to store the partial expression.
T      F
balancing symbols指的是⼀组匹配的符号，类似于圆括号，花括号，⽅括号。可见这道题的意思是求解逆波兰表达式，使⽤stack⽽⾮queue。
5.To sort N distinct records by bubble sort, the number of record swaps must reach its maximum when the original sequence is almost in sorted order.
T      F
冒泡排序的record swaps取决于逆序对的数量，对于⼀个已经排序过的序列，逆序对的数量可以是0或者最⼤，逆序对的数量可能最⼤也可能最⼩。
6.To sort N records by simple selection sort, the numbers of comparisons and record movements are O(N2) and O(N), respectively.
F
⽐较次数的计算：(n-1)+(n-2)+...+2+1。共⽤n2/2次。移动只在⼀轮⽐较完成后，所以就算每次都需要移动，⼀共也才(n-1)次，所以⽐较可以看作O(N2)，移动可以看作O(N)。
7.(neuDS)算法必须有输出，但可以没有输⼊。
F
算法有0个或多个输⼊，以刻画运算对象的初始情况；算法有⼀个或多个输出，以反映对输⼊数据加⼯后的结果。
8."Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array.
T      F
循环队列是⼀个抽象的概念，不局限于实现⽅式。
9.对于⼀个随机算法，其最坏情况下的运⾏时间等于运⾏时间期望值的常数倍。
虽然我们希望如此，因为这会使算法⽐较稳定，但⼤多数算法的运⾏时间期望值是最优和最差的情况的折中。
10.For a sequentially stored linear list of length N, the time complexities for query and insertion are O(1) and O(N), respectively.
F
顺序存储的线性表⽀持随机存取，所以查询的时间是常数时间，但插⼊需要把后⾯每⼀个元素的位置都进⾏调整，所以是线性时间。
11.The Fibonacci number sequence {F N} is defined as: F0=0, F1=1, F N=F N-1+F N-2, N=2, 3, .... The space complexity of the function which calculates F N recursively is O(logN).
T      F
为了求F N，需要从F0到F N的值，需要O(N)。
12.斐波那契数列F N的定义为：F0=0, F1=1, F N=F N-1+F N-2, N=2, 3, …。⽤递归函数计算F N的空间复杂度是O(logN)。
13.(neuDS)数据的物理结构是指数据在计算机中的实际存储形式。
F
物理结构和计算机的硬件直接相关。
14.If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output s
equence {3, 4, 1, 2, 5}.
F
FIFO结构。
15.If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest.
F
频繁地对最后⼀个元素查删，顺序表完全可以胜任。
16.For the following piece of code
if ( A > B ){
for ( i=0; i<N*2; i++ )
for ( j=N*N; j>i; j-- )
C += A;
}
else {
for ( i=0; i<N*N/2; i++ )
for ( j=N; j>i; j-- )
for ( k=0; k<N*100; k++)
C += B;
}
the lowest upper bound of the time complexity is O(N5)
T      F
最多是O(N4)。
17.If keys are pushed onto a stack in the order abcde, then it's impossible to obtain the output sequence cdabe.
F
18.If N numbers are stored in a doubly linked list in increasing order, then the average time complexity for binary search is O(logN).
即使双链表还是⽆法通过下标查询，速度依然不可能到达O(logN)。
19.Given the input sequence onto a stack as {1, 2, 3, ..., N}. If the first output is i, then the j-th output must be j-i-1.
T      F
除⾮能保证序列在完全⼊栈前都不出栈。
20.⽤动态规划⽽⾮递归的⽅法去解决问题时，关键是将⼦问题的计算结果保存起来，使得每个不同的⼦问题只需要被计算⼀次。⼦问题的解可以被保存在数组或哈希散列表中。
F
21.Let S be the set of activities in Activity Selection Problem. The greedy rule of "collecting the activity that starts the latest" is correct for finding a maximum-size subset of mutually compatible activities of S.
F
贪婪算法适⽤于通过求解局部最优解获得全局最优解的情况。和题⽬描述相符合。
22.(neuDS_C++)空串与空格串是相同的。
23.(neuDS)线性表的逻辑顺序和存储顺序总是⼀致的。
24.(nueDS_C++)如果⼀个串中的所有字符均在另⼀串中出现，则说前者是后者的⼦串。
注意串的序列性。
25.(neuDS)单链表不是⼀种随机存取的存储结构。
F
26.设只包含根结点的⼆叉树⾼度为0，则⾼度为k的⼆叉树最⼩结点数为k+1。
F
27.⼆叉树通常有顺序存储结构和链式存储结构。
F
28.存在⼀棵总共有2016个结点的⼆叉树，其中有16个结点只有⼀个孩⼦。
T      F
假设⼆叉树的结点拥有0个，1个，2个孩⼦的结点分别为N0，N1，N2。⾸先，需要了解，⼆叉树中度为2的结点数量⽐叶节点少⼀，那么
N0+N1+N2=2016⇒N1+2N2+1=2016⇒N1+2N2=2015，看来N1必须是奇数。
29.具有10个叶结点的⼆叉树中，有9个度为2的结点。
F
参考上⼀题的分析。
30.An algorithm to check for balancing symbols in an expression uses a stack to store the symbols.
F
参考第四题。
选择题
1.If a linear list is represented by a linked list, the addresses of the elements in the memory:
A.must be consecutive
B.may or may not be consecutive
C.must be consecutive for part of the elements
D.must be nonconsecutive
2.If the most commonly used operations are to insert a new element after the last element, and to delete the first element in a linear list, then which of the following data structures is the most efficient?
A.singly linked list
B.singly linked circular list with a tail pointer
C.singly linked circular list with a head pointer
D.doubly linked list
循环链表的尾指针可以很快地到头指针，头指针却不能很快地到尾指针
3.When is the linked list structure suitable for representing a linear list L?
A.frequently insert into and delete from L
B.frequently change the key values of the nodes in L
C.L contains large amount of nodes
D.the structure of the nodes in L is complicated
链表适合插⼊和删除
4.The best "worst-case time complexity" for any algorithm that sorts by comparisons only is:
A.O(logN)
B.O(N)
C.O(NlogN)
D.O(N2)
对于⽐较排序算法，堆排序和归并排序的最坏时间复杂度都是O(NlogN)。
5.To sort N distinct elements in descending order by bubble sort, under which condition of the elements that the method will make the most number of swaps?
C.unsorted
D.almost sorted
当数据是升序排序时，执⾏降序排序的逆序对数量最多，交换次数也最多。
6.To sort N elements by simple selection sort, the numbers of comparisons and movements are:
A.O(N2), O(N)
B.O(N), O(logN)
C.O(logN), O(N2)
D.O(NlogN), O(NlogN)
参考判断题第六题对选择排序的分析。
7.Use simple insertion sort to sort 10 numbers from non-decreasing to non-increasing, the possible numbers of comparisons and movements are:
A.100, 100
B.100, 54
C.54, 63
D.45, 44
插⼊排序的⽐较次数为(n−1)+(n−2)+...+1=n(n−1)
2，交换次数⼀定⽐⽐较次数低，所以选择D。
8.Since the speed of a printer cannot match the speed of a computer, a buffer is designed to temperarily store the data from a computer so that later the printer can retrieve data in order. Then the proper structure of the buffer shall be a:
A.stack
B.queue
<
9.Represent a queue by a singly linked list. Given the current status of the linked list as 1->2->3 where x->y means y is linked after x. Now if 4 is enqueued and then a dequeue is done, the resulting status must be:
A.1->2->3
B.2->3->4
C.4->1->2
D.the solution is not unique
10.Use binary search to find a number from 100 sorted numbers, the worst-case number of comparisons is:
A.7
B.10
C.50
D.99
11.Given the rucurrent equations for the time complexity of a program as: T(1)=1, and T(N)=2T(N/2)+N. Then the time complexity must be:
A.O(logN)
B.O(N)
D.O(N2)
为了获得T(N)，需要计算递归等式logN次，2T(N/2)计算logN次后就等于N，N计算logN次后等于NlogN，两边取⼤的⼀⽅，最终的结果就是NlogN。
12.The recurrent equations for the time complexities of programs P1 and P2 are:
P1: T(1)=1, T(N)=T(N/2)+1;
P2: T(1)=1, T(N)=2T(N/2)+1;
Then the correct conclusion about their time complexities is:
A.they are both O(logN)
D.O(logN) for P1, and O(NlogN) for P2
P1的加号左边经过logN次递归等式计算恒等于1，⽽右边每次递归等式都加1，经过logN次计算最后为logN，两边取⼤是logN；
P2加号的左边经过logN次递归等式计算是N，右边每次递归等式都加1，经过logN次计算最后为logN，两边取⼤总体为N。
13.For a sequentially stored linear list of length N, the time complexities for query and insertion are:
A.O(1), O(1)
B.O(1), O(N)
C.O(N), O(1)
D.O(N), O(N)
14.For a sequentially stored linear list of length N, which of the following operations has the time complexity O(1)?
A.visit the i-th (1≤i≤N) node and find the immediate predecessor of the i-th (2≤i≤N) node
B.insert a new node after the i-th (1≤i≤N) node
C.delete the i-th (1≤i≤N) node
D.sort the N nodes in increasing order
15.切原⽊问题：给定⼀根长度为N⽶的原⽊；另有⼀个分段价格表，给出长度L=1,2,...,M对应的价格P L。要求你出适当切割原⽊分段出售所能获得的最⼤收益R N。例如，根据下⾯给出的价格表，若要出售⼀段8⽶长的原⽊，最优解是将其切割为2⽶和6⽶的两段，这样可以获得最⼤收益R8=P2+P6=5+17=22。⽽若要出售⼀段3⽶长的原⽊，最优解是根本不要切割，直接售出。
Length L12345678910
Price P L1589101717202328
下列哪句陈述是错的？
A.此问题可以⽤动态规划求解
B.若N≤M，则有R N=max{P N,max1<=i<N{R i+R N-i}}
C.若N>M，则有R N=max1<=i<N{R i+R N-M}
D.算法的时间复杂度是O(N2)
N>M时，应该为R N=max1<=i{R
i+R M-i}
16."⼆叉树为空"意味着⼆叉树（）。
A.由⼀些没有赋值的空结点构成
B.根结点没有⼦树
C.不存在
D.没有结点
17.栈和队列的共同点( )。
A.都是先进先出
B.都是后进先出
只允许在端点处插⼊和删除元素
没有共同点
sort of等于什么18.⼴义表是⼀种（）数据结构。
A.⾮递归的
B.递归的
C.树型
D.图状
⼴义表容许表中的元素拥有⾃⼰的数据结构，使⽤递归的⽅式定义，所以是递归的数据结构。
19.若串S="software"，其⼦串的数⽬是
A.8
B.37
C.36
D.9
⼦串包含空串。
20.What is the major difference among lists, stacks, and queues?
A.Lists use pointers, and stacks and queues use arrays
B.Stacks and queues are lists with insertion/deletion constraints
C.Lists and queues can be implemented using circularly linked lists, but stacks cannot
D.Lists are linear structures while stacks and queues are not
21.线性表是⼀个（）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。