一、单项选择题。
1．若让元素1，2，3，4依次进栈，则出栈次序不可能出现___的情况。
a．3，2，1，4 b．2，1，4，3 c．4，3，2，1 d．1，4，2，3
2．在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加___
a．2 b．1 c．0 d．-1
3．利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为___
a．55b．29c．58d．38
4．若一个图的边集为，则从顶点a开始对该图进行广度优先搜索，得到的顶点序列可能为___
a．abcdef b．abcfde c．abdcef d．acbfde
5．若根据查找表（23，44，36，48，52，73，64，58）建立线性哈希表，采用h（k）=k%13计算哈希地址，则元素64的哈希地址为___
a．4 b．8 c．12 d．13
6．假定对元素序列（7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。偷懒方法。
a．2 b．3 c．4 d．5
7．操作系统中，__负责对进程进行调度。
a．处理机管理 b． 作业管理 c．高级调度管理 d． 存储和设备管理。
8．进程与程序的主要区别是：__
．进程是静态的；而程序是动态的。
．进程不能并发执行而程序能并发执行。
．程序异步执行，会相互制约，而进程不具备此特征。
．进程是动态的，而程序是静态的。
9．虚拟存储管理策略可以。
a．扩大逻辑内存容量b．扩大物理内存容量
c．扩大逻辑外存容量d．扩大物理外存容量。
二、填空题。
1．在一个单链表中指针p所指向结点的后面插入一个指针q所指向的节点时，首先___然后___
2．一个顺序循环队列存在于a[m]中，假定队首和队尾指针分别为front和rear，则判断队空的条件为判断队满的条件为。
3．在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为___
4．有如图所示的一棵二叉树，则该二叉树的中序遍历序列为。
5．假定一个有向图的顶点的集为，边集，则出度为0的顶点个数为___入度为1的顶点个数为___
6．操作系统是计算机系统内部各种硬件和软件资源、有效地组织多道程序运行的系统软件（或程序集合），是用户和计算机的接口。
7．在一段时间内，只允许一个进程访问的资源称为。
8．进程存在的标志是。
9．内存中各存储单元的地址是从统一的基地址顺序编址，这种地址称为。
10存储管理方式能使存储碎片尽可能少，而且使内存利用率较高。
三、应用题。
1．对于如图所示的有向图，请给出对应的邻接矩阵和邻接表。
2．设有权值6，10，13，14，20，37，依照下面的程序算法在**写出数据的变化过程，并画出所构造的哈夫曼树。
算法如下：huffman(n,l child,r child,data,prnt,w)
/ date:存放结点权值，l child:左指针，r child:
右指针，prnt:双亲指针，w[1:n]存放n个权值，l child[1:
m],r child[1:m],data[1:m],prnt[1:
m],m=2n-1//
1．for i=1 to n
2． data[i]←w[i];l child(i)←0;r child(i)←0 //初始化//
3．end(i)
4．for i=1 to (2*n-1) prnt[i]←0//初始化//
5．end(i)
6．for k=n+1 to (2*n-1)
7． select(k-1,i,j)//从data[1:k-1]中选出双亲为零的两个权值最小的下标i,j//
8． data[k]←data[i]+date[j]
9． l child[k]←i; r child[k]←j;
10． prnt[i]←k; prnt[j]←k;
11．end(k)
12．return
3．写出如图所示稀疏矩阵的三元组表示的数组以及转置后矩阵的两个辅助向量pot和nun。
4．在请求分页系统中，某用户的编程空间为16个页面，每页1k，分配的内存空间为8k。假定某时刻该用户的页表如图所示(h表示为十六进制)，试问：
1）逻辑地址084b（h）对应的物理地址是多少？（用十六进制表示）
2）逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示）
3）当该用户进程欲访问24a0（h）单元时，会出现什么现象？
四、算法题。
设有一台计算机，有两条i/o通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区b1中，加工处理后在搬到缓冲区b2中，并在打印机上印出，问：
系统要设几个进程来完成这个任务？各自的工作是什么？
这些进程间有什么样的相互制约关系？
用p、v操作写出这些进程的同步互斥算法。
2023年软件技术基础复习题 作业
工程软件技术基础复习题 04级 1.什么是数据结构？什么是算法？数据结构对算法有什么影响？2.设一棵二叉树的中序和后序遍历为。中序 bdceafhg 后序 decbhgfa 画出这棵二叉树的逻辑结构，并写出线序遍历结果。3.对下列数据 18,27,5,89,13,7,190,57,33,29,131...
软件技术基础考试复习大纲 2019
数据结构部分。1 第一章绪论。章节 4知识点 数据结构 数据结构的研究内容 算法 算法的基本特性 算法分析的内容 时间复杂度分析 2 第二章线性表 重点 章节 5知识点 线性表的顺序存储结构及其操作 线性表的链式存储结构及其操作 如何选择线性表的存储结构 3 第四章堆栈和队列。章节 7知识点 堆栈 ...
2019软件技术基础2019复习提纲
软件技术基础2011 1207复习提纲。c语言基本语法。进程与程序。临界区与程序。进程的状态及其转变。进程时间片。存储管理中的地址转换。死锁的必要条件。文件记录的随机访问。文件物理结构。可行性分析阶段。概要设计阶段。需求分析阶段。详细设计阶段。类。类的数据成员。对象 标识 操作 消息 状态。ui部件...