一、单项选择题：(共12题，24分)
|
1、
串是一种特殊的线性表，其特殊性体现在（ ）。
|
|
可以顺序存储 |
|
数据元素是一个字符 |
|
可以链式存储 |
|
数据元素可以是多个字符若 |
|
|
2、
串下面关于串的的叙述中，（ ）是不正确的？
|
|
串是字符的有限序列 |
|
空串是由空格构成的串 |
|
模式匹配是串的一种重要运算 |
|
串既可以采用顺序存储，也可以采用链式存储 |
|
|
3、
串的长度是指（ ）。
|
|
串中所含不同字母的个数 |
|
串中所含字符的个数 |
|
串中所含不同字符的个数 |
|
串中所含非空格字符的个数 |
|
|
4、
假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（ ）。
|
|
808 |
|
818 |
|
1010 |
|
1020 |
|
|
5、
设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（ ）。
|
|
BA+141 |
|
BA+180 |
|
BA+222 |
|
BA+225 |
|
|
6、
二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。
|
|
A[8,5] |
|
A[3,10] |
|
A[5,8] |
|
A[0,9 |
|
|
7、
设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ ）。
|
|
(i-1)*n+j |
|
(i-1)*n+j-1 |
|
i*(j-1) |
|
j*m+i-1 |
|
|
8、
数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。
|
|
55 |
|
45 |
|
36 |
|
16 |
|
|
9、
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
|
|
13 |
|
32 |
|
33 |
|
40 |
|
|
10、
若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i
|
|
i*(i-1)/2+j |
|
j*(j-1)/2+i |
|
i*(i+1)/2+j |
|
j*(j+1)/2+i |
|
|
11、
广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。
|
|
(g) |
|
(d) |
|
c |
|
d |
|
|
12、
设广义表L=((a,b,c))，则L的长度和深度分别为（ ）。
|
|
1和1 |
|
1和3 |
|
1和2 |
|
2和3 |
|
|
二、简答题：(共4题，20分)
|
1、
写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
|
|
|
|
2、
编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）
|
|
|
|
3、
数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：
① 存放该数组所需多少单元？
② 存放数组第4列所有元素至少需多少单元？
③ 数组按行存放时，元素A[7,4]的起始地址是多少？
④ 数组按列存放时，元素A[4,7]的起始地址是多少？
|
|
|
|
4、
请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
|
|
|
|
三、问答题：(共1题，5分)
|
1、
写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。
|
|
|
|
|