发布时间 : 星期三 文章2015年下半年上午 程序员 试题及答案与解析-软考考试真题-基础知识更新完毕开始阅读8303cc2bf11dc281e53a580216fc700aba685205
全国计算机技术与软件专业技术资格（水平）考试库
china_nejcer
第j列），排在它之前的元素有i-1个，因此，a[i,j]之前共有(j-1)*m+i-1个元素。
数组中指定元素的存储位置相对于数组空间首地址的偏移量等于k*d，其中k为排在该元素前的元素个数，d为每个元素占用的存储单元数。
? 第35题.以下关于字符串的叙述中，正确的是(35)。
A.字符串属于线性的数据结构 B.长度为0字符串称为空白串
C.串的模式匹配算法用于求出给定串的所有子串 D.两个字符串比较时，较长的串比较短的串大 【参考答案】A
【答案解析】一个线性表是n个元素的有限序列（n≥0）。由于字符串是由字符构成的序列，因此符合线性表的定义。
选项B是错误的。长度为0字符串称为空串（即不包含字符的串〉，而空白串是指由空白符号（空格、制表符等〉构成的串，其长度不为0。
选项C是错误的。串的模式匹配算法是指在串中查找指定的模式串是否出现及其位置。
选项D是错误的。两个字符串比较时，按照对应字符（编码）的大小关系进行比较。
? 第36题.按照逻辑关系的不同可将数据结构分为(36)。
A.顺序结构和链式结构 B.顺序结构和散列结构 C.线性结构和非线性结构 D.散列结构和索引结构 【参考答案】C
【答案解析】在数据结构中，顺序结构和链式结构是两种基本的存储结构。线性结构和非线性结构是按照逻辑关系来划分的。
? 第37题.若栈采用链式存储且仅设头指针，则(37)时入栈和出栈操作最方便。
A.采用不含头结点的单链表且栈顶元素放在表尾结点 B.采用不含头结点的单链表且栈顶元素放在表头结点
C.采用含头结点的单循环链表且栈顶元素随机存放在链表的任意结点 D.采用含头结点的双向链表且栈顶元素放在表尾结点 【参考答案】B
【答案解析】栈的操作要求是后进先出，而且仅在表尾一端加入和删除元素。对单链表进行操作时，必须从头指针出发。根据栈的操作要求，单循环链表和双向链表都是没有必要的，而且选项C中将栈顶元素任意存放是错误的。
可以采用单链表作为栈的存储结构，将表头作为栈顶来使用。
含头结点的单链表如下图所示，其中La为头指针，La指向的结点为头结点。
2015年下半年上午-程序员-上午试题及答案与解析（软考真题-基础知识）13/28
全国计算机技术与软件专业技术资格（水平）考试库
china_nejcer
不含头结点且栈顶元素放在表尾结点的单链表如下图所示，其中La为头指针，La指向的结点存储了先进入栈且没有出栈的元素。显然，因为要从La出发遍历至表尾才能进行入栈和出栈操作，在这种情况下出栈和入栈都是最低效的，时间复杂度都是O（n）。
如果采用不含头结点且找顶元素放在表头的单链表，如下图所示，出栈和入栈操作都在表头，时间复杂度都为O（1）。
? 第38题.三个互异的元素a、b、c依次经过一个初始为空的栈后，可以得到(38)种出
栈序列。
A.6 B.5 C.3 D.1 【参考答案】B
【答案解析】a、b、c三个互异元素构成的全排列有6种，为abc,acb,bac,bca，cba，cab。如果入栈顺序为abc，则除了cab，其他序列都可通过合法的入栈和出栈操作排列得到。
? 第39题.最优二叉树（或哈夫曼树）是指权值为w1,w2，…,wn的n个叶结点的二叉树
中带权路径长度最小的二叉树。（39）是哈夫曼树（叶结点中的数字为其权值）。
A.
B.
2015年下半年上午-程序员-上午试题及答案与解析（软考真题-基础知识）14/28
全国计算机技术与软件专业技术资格（水平）考试库
china_nejcer
C.
D.
【参考答案】A
【答案解析】哈夫曼树又称为最优二叉树，是一类带权路径长度最短的树。 树的带权路径长度（WPL)为树中所有叶子结点的带权路径长度之和，记为
其中n为带权叶子结点数目，wk为叶子结点的权值，lk为根到叶子结点的路径长度。 选项A所示二叉树的WPL=(2+4)*3+5*2+7*1=35 选项B所示二叉树的WPL=(2+4+5+7)*2=36 选项C所示二叉树的WPL=(5+7)*3+4*2+2*1=46 选项D所示二叉树的WPL=(4+5）*3+7*2+2*1=43
? 第40题.某有向图G及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，
错误的是（40）。
A.有向图的邻接矩阵可以是对称矩阵 B.第i行的非零元素个数为顶点i的出度 C.第i行的非零元素个数为顶点i的入度
D.有向图的邻接矩阵中非零元素个数为图中弧的数目 【参考答案】C
【答案解析】图中顶点v的度是指关联于该顶点的边的数目，若为有向图，顶点的度表示该顶点的入度和出度之和。
图的邻接矩阵表示法利用一个矩阵来表示图中顶点之间的关系。矩阵元素的值设置如下：
2015年下半年上午-程序员-上午试题及答案与解析（软考真题-基础知识）15/28