计算机软件基础习题及答案.pdf资源-CSDN文库

习题一

1. 什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举

例说明。

2. 数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？

3. 设

n

为正整数 , 分析下列各程序段中加下划线的语句的执行次数。

(1) for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

c[i][j] = 0.0;

for (int k = 1; k <= n; k++)

c[i][j] = c[i][j] + a[i][k] * b[k][j];

}

(2) x = 0; y = 0;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= i; j++)

for (int k = 1; k <= j; k++)

x = x + y;

(3) int i = 1, j = 1;

while (i<=n && j<=n) {

i = i + 1; j = j + i;

}

(4)

*

int i =1;

do{

for (int j = 1; j <= n; j++)

i = i + j;

}while(i<100 + n);

4. 试编写一个函数计算 n!*2

n

的值，结果存放于数组 A[arraySize] 的第 n 个数组元素中， 0

n arraySize 。若设计算机中允许的整数的最大值为 maxInt ，则当 n>arraySize 或者对于

某一个 k (0 k n) ，使得 k!*2

k

> maxInt 时，应按出错处理。可有如下三种不同的出

错处理方式：

(1) 用 printf 显示错误信息及 exit (1) 语句来终止执行并报告错误；

(2) 用返回整数函数值 0, 1 来实现算法，以区别是正常返回还是错误返回；

(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。

试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。

5. 设有一个线性表 (a 0, a 1, …, a n-2 , a n-1 ) 存放在一个一维数组 A[arraySize] 中的前 n 个

数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前 n 个原址内容置换为

(a

n-1

, a

n-2

, …, a

1

, a

0

) 。最后分析此算法的时间复杂度及空间复杂度。

6. 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下 , 对有 127

个元素的顺序表进行插入 , 平均需要移动多少个元素 ? 删除一个元素 , 又平均需要移动多

少个元素 ?

7. 利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析 (2)

与(3) 的时间复杂度出现差异的原因。

(1) 从顺序表中删除具有给定值 x 的所有元素。

(2) 从顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t ）的所有元素。

(3) 从有序顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t ）的所有元素。

(4) 将两个有序顺序表 la,lb 合并成一个新的有序顺序表 lc 。

(5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

8. 线性表可用顺序表或链表存储。试问：

(1) 两种存储表示各有哪些主要优缺点 ?

(2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数

也可能自动改变、在此情况下，应选用哪种存储表示？为什么？

(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元

素，这时，应采用哪种存储表示？为什么？

9. 试写出计算线性链表长度的算法。

10. 设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有

结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一个

结点。

11. 设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链

表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。

12．设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针 , 试设计一个算法 ,

将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存

储空间 , 不另外占用其它的存储空间。表中允许有重复的数据。

13．设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针 , 试设计一个算法 ,

将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存

储空间 , 不另外占用其它的存储空间。表中允许有重复的数据。

14. 在一个循环链表中寻找值为 x 的结点，并将该结点移到第一个结点之前。

15. 对于下面的每一步，画出栈元素和栈顶指针的示意图：

（1）栈初始化；

（2）元素 x 入栈；

（3）元素 y 入栈；

（4）出栈

（5）栈初始化

（6）元素 z 入栈

16. 铁路进行列车调度时 , 常把站台设计成栈式结构的站台，如

右图所示。试问：

(1) 设有编号为 1,2,3,4,5,6 的六辆列车 , 顺序开入栈式

结构的站台 , 则可能的出栈序列有多少种 ?

(2) 若进站的六辆列车顺序如上所述 , 那么是否能够得到

435612, 325641, 154623 和 135426 的出站序列 , 如果不能 , 说明为什么不能 ; 如果能 , 说

明如何得到 ( 即写出 " 进栈 " 或" 出栈 " 的序列 ) 。

17. 试证明：若借助栈可由输入序列 1, 2, 3, …, n 得到一个输出序列 p1, p2, p3, …, pn ( 它

是输入序列的某一种排列 ) ，则在输出序列中不可能出现以下情况，即存在 i < j < k ，使

得 p

j

< p

k

< p

i

。(提示：用反证法 )

18. 将编号为 0 和 1 的两个栈存放于一个数组空间 V[m] 中，栈底分别处于数组的两端。当第

0 号栈的栈顶指针 top[0] 等于 -1 时该栈为空，当第 1 号栈的栈顶指针 top[1] 等于 m时该栈

为空。两个栈均从两端向中间增长。当向第 0 号栈插入一个新元素时，使 top[0] 增 1 得到

新的栈顶位置，当向第 1 号栈插入一个新元素时，使 top[1] 减 1 得到新的栈顶位置。当

top[0]+1 == top[1] 时或 top[0] == top[1]-1 时，栈空间满，此时不能再向任一栈加入新

的元素。试定义这种双栈 (Double Stack) 结构的类定义，并实现判栈空、判栈满、插入、删

除算法。

19. 改写顺序栈的进栈成员函数 Push(x) ，要求当栈满时执行一个 stackFull( ) 操作进行栈

满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原

来栈数组中的元素占据新数组的前 MaxSize 位置。

20. 根据教案中给出的优先级，回答以下问题：

(1) 在表达式求值的过程中，如果表达式 e 含有 n 个运算符和分界符，问操作数栈 (NS)

中最多可存入多少个元素？

(2) 如果表达式 e 含有 n 个运算符，且括号嵌套的最大深度为 6 层，问栈中最多可存入

多少个元素？

21. 表达式的中缀表示为 a * x - b / x^2 ，试利用栈将它改为后缀表示 ax * bx2^/ - 。写

出转换过程中栈的变化。 (^ 表示乘方运算 )

22. 设循环队列的容量为 70（序号从 1 到 70），经过一系列入队和退队运算后，有：

（1）front=15 ，rear=46 ；

（2）front=45 ，rear=10

问在上述两种情况下，循环队列中各有多少个元素？

23. 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试

编写基于此结构的队列的插入 (enqueue)和删除 (dequeue)算法，并给出队列空和队列满的条件。

习题三

1. 设有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677,

765, 897, 908 。试画出对其进行折半查找时的二叉查找树 , 并计算查找成功的平均查找长

度和查找不成功的平均查找长度。

2. 若对有 n 个元素的有序顺序表和无序顺序表进行顺序查找 , 试就下列三种情况分别讨论

两者在等查找概率时的平均查找长度是否相同 ?

(1) 查找失败 ;

(2) 查找成功 , 且表中只有一个关键码等于给定值 k 的对象 ;

(3) 查找成功 , 且表中有若干个关键码等于给定值 k 的对象 , 要求一次查找找出所有

对象。

3. 设有 10000 个记录对象 , 通过分块划分为若干子表并建立索引 , 那么为了提高查找效率 ,

每一个子表的大小应设计为多大 ?

4. 设散列表为 HT[13], 散列函数为 H ( key) = key %13。用闭散列法解决冲突 , 对下列关

键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。

(1) 采用线性探测法寻找下一个空位 , 画出相应的散列表 , 并计算等概率下查找成功

的平均查找长度和查找不成功的平均查找长度。

(2) 采用随机探测法寻找下一个空位 , 随机数序列为： 5，4，2，7，3，6，…。画出相

应的散列表 , 并计算等概率下查找成功的平均查找长度。

5. 设有 150 个记录要存储到散列表中 , 要求利用线性探查法解决冲突 , 同时要求找到所需

记录的平均比较次数不超过 2 次。试问散列表需要设计多大？设是散列表的装载因子，

则有

)

1

1(

2

1

ASL

succ

6. 设有 15000 个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个

页块可存放 30 个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超

过 1.5 次，则该文件应设置多少个桶？已知，链地址法的平均查找长度 ASL=1+α/2

7. 设待排序的排序码序列为 {12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用

以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。

(1) 直接插入排序 (2) 希尔排序 ( 增量为 5,2,1) (3) 冒泡排序

(4) 快速排序 (5) 直接选择排序 (6) 堆排序

(7) 二路归并排序

8. 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在

快速排序过程中有这种现象吗？

9. 试设计一个算法 , 使得在 O(n) 的时间内重排数组 , 将所有取负值的排序码排在所有取

正值 ( 非负值 ) 的排序码之前。

剩余35页未读，继续阅读

计算机软件基础习题及答案.pdf

计算机软件基础.pdf

计算机软件基础课后习题答案.pdf

计算机基础第2版习题参考答案.pdf

计算机软件技术基础习题与参考答案.pdf

计算机软件技术基础(第三版)习题答案.pdf

022432022年自考计算机软件基础(一)练习题及答案参考.pdf

计算机软件基础1.pdf

计算机软件技术基础第三版习题答案.pdf

《计算机应用基础》练习题1.pdf

自考2243-计算机软件基础(-)课后习题答案.pdf

计算机软件基础(-)课后习题答案归类.pdf

答案[计算机软件技术基础].pdf

计算机硬件和计算机软件习题及答案.pdf

计算机软件基础(二).pdf

JDK 1.8 64位.rar

SoftCnKiller2.54.zip（因为要下载码，弃用不更新了）

编译好的64位pycdc.exe(支持python3.10和python3.11)

最新资源