计算机软考：软件设计师练习试题及答案解析(6)

　　84. 在最好和最坏情况下的时间复杂度均为O(nlogn)，但不稳定的排序算法是 (89) 。

　　(89) A.堆排序

　　B.快速排序

　　C.归并排序

　　D.基数排序

　　参考答案：(89)A。

　　解析：堆排序在最好和最坏情况下的时间复杂度均为O(nlogn)但不稳定。

　　快速排序最好和最坏情况下的时间复杂度分别为O(n2)和O(nlogn)且不稳定。

　　归并排序是在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法。

　　基数排序在最好和最坏情况下的时间复杂度均为O(d(n+rd))。

　　85. 利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图G=共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(I,j)即为图G 中节点i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度)，则求解该问题的递推关系式为 (90) 。

　　(90) A.Dk(I,j)=Dk-1(I,j)+C(I,j)

　　B.Dk(I,j)=Dk-1(I,k)+Dk-1(k,j)

　　C.Dk(I,j)=min{Dk-1(I,j),Dk-1(I,j)+C(I,j)}

　　D.Dk(I,j)=min{Dk-1(I,j),Dk-1(I,k)+Dk-1(k,j)}

　　参考答案：(90)D。

　　解析：设Pk(I,j)表示从i到j并且不经过编号比k还大的节点的最短路径，那么Pk(I,j)有以下两种可能。

　　① Pk(I,j)经过编号为k的节点，此时Pk(I,j)可以分为从i到k和从k至j的两段，易知Pk(I,j)的长度为Dk-1(I,k)+Dk-1(k,j)。

　　② Pk(I,j)不经过编号为k的节点，此时Pk(I,j)的长度为Dk-1(I,j)。

　　因此，求解该问题的递推关系式为：Dk(I,j)=min{Dk-1(I,j),Dk-1(I,k)+Dk-1(k,j)}。

　　86. 通常， (91) 应用于保护被中断程序现场等场合。

　　(91) A.队列

　　B.堆栈

　　C.双链表

　　D.数组

　　参考答案：(91)B。

　　解析：在计算机中，堆栈被定义为一段特殊的内存区。其存取数据的特点是先进后出(FILO)。这一特点使它最常用于保护被中断程序的现场等应用场合。

　　87.若有说明语句“inta[10]，*p=a;”，对数组元素的正确引用是(92)

　　(92) A. a[p]

　　B. P[a]

　　C. *(P+2)

　　D. P+2

　　参考答案：(91)C。

　　解析：在C语言中，约定数组名单独出现在表达式中时，它表示数组首元素的指针。有inta[10]，则a可以作为&a[0]使用。另有整型指针变量p，代码p=a实现p指向数组a的首元素。则表达式*(p+2)是引用数组元素a[2]。表达式a[p]和p[a]都是不正确的，下标必须是整型表达式，不可以是指针表达式。表达式p+2是指针表达式，它的值是&p[2]。所以只有表达式*(p+2)引用数组a的元素a[2]。所以解答是C。

　　88.下面各语句中，能正确进行赋字符串操作的语句是(93)

　　(93) A. chars[5]={"ABCDE"};

　　B. chars[5]={’A’,’B’,’C’,’D’,’E’};

　　C. char*s;s="ABCDE";

　　D. char*s;scanf("%"，s);

　　参考答案：(93)C。

　　解析：字符串最终存储于字符数组中，存储字符串的字符数组可以是程序主动引入的(定义或动态分配)，也可以是字符串常量，由系统分配。其中字符数组用字符串初始化就是字符串存储于由程序引入的字符数组的例子。给字符指针赋字符串则是系统自动分配字符率存储空间的例子。给字符指针赋字符串并不是将一个长长的字符串存于字符指针变量中，而是将字符串常量存储于常量区，并将存储这个字符串的首字节地址赋给指针变量，让指针变量指向字符率常量的首字符。对于以字符串作为字符数组初值的情况，要求字符数组足够的大，能存得下字符串常量。这里有一个特别的规定，若数组的大小少于存储字符串有效字符的字节个数，系统将报告错误;当字符数组的大小只能存储字符串的有效字符，而不能存储字符率结束标记符时，则存储于字符数组中的内容是字符序列，因没有存储字符率结束标记符，存储的内容就不是字符串。如代码chara[5]="ABCDE"。

　　另外，给字符数组元素逐一赋字符初值，并在字符初值中没有字符串结束标记符，则存于字符数组中的内容也不是字符率。如代码chars[5]={’A’，’B’，’C’，’D’，’E’}。特别要注意当字符指针还未指向某个字符数组的元素时，不可以通过字符指针输入字符串。如代码char*s;scanf("%s"，s)。若写成char*str;scanf("%s"，&str)更是错误的了。

　　由于C语言规定数组不能相互赋值，所以只能将字符串常量赋给某字符指针。如代码char*s;s="ABCDE"是正确的。实际上，字符率"ABCDE"被存储于常量区中，向指针变量赋的是字符指针，让s指向其中的字符’A’。所以解答是C。