免费智能真题库 > 历年试卷 > 软件设计师 > 2025年上半年 软件设计师 下午试卷 案例
  第3题      
  知识点：   队列   数据类型   指针   基本操作   空指针   排序   拓扑排序

 
对有向图进行拓扑排序的方法是：
（1）初始时拓扑序列为空；
（2）任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点 以及从该顶点出发的弧：
（3）重复（2），直到不存在入度为0的顶点为止（若所有顶点都进入拓扑序列则完 成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。
函数int* TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为vl，v2,…，vn,图G采用邻接表表示，其数据类型定义如下：

例如，某有向图G如图4-1所示，其邻接表如图4-2所示。

函数TopSort中用到了队列结构（Queue的定义省略)，实现队列基本操作的函数原型如下表所示：
 
问题：3.1   根据以上说明和C代码，填充C代码中的空（1)〜（5)。
 
问题：3.2   对于图4-1所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数 TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。
 
问题：3.3   设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是（6）。
若有向图采用邻接矩阵表示（例如，图4-1所示有向图的邻接矩阵如图4-3所示），且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是（7）。
 
 
 

   知识点讲解    
   · 队列    · 数据类型    · 指针    · 基本操作    · 空指针    · 排序    · 拓扑排序
 
       队列
        1）队列的定义及基本运算
        队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。
        对队列进行的基本操作如下。
        （1）置队空InitQueue(Q)：创建一个空的队列Q。
        （2）判队空Empty(Q)：判断队列是否为空。
        （3）入队EnQueue(Q,x)：将元素x加入到队列Q的队尾，并更新队尾指针。
        （4）出队DeQueue(Q)：将队头元素从队列Q中删除，并更新队头指针。
        （5）读队头元素Frontque(Q)：返回队头元素的值，但并不更新队头指针。
        2）队列的存储结构
        （1）顺序存储。队列的顺序存储结构是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行，因此设置队头指针和队尾指针，分别指示当前的队首元素和队尾元素。
        在顺序队列中，为了降低运算的复杂度，元素入队时只需修改队尾指针，元素出队时只需修改队头指针。由于顺序队列的存储空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到其上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。此时，可通过整除取余运算将顺序队列假想成一个环状结构，称之为循环队列。在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的。为了区别队空和队满的情况，可采用两种处理方式：其一是设置一个标志位，以区别头、尾指针的值相同时队列是空还是满；其二是牺牲一个元素空间，约定以"队列的尾指针所指位置的下一个位置是头指针时"表示队列满，头、尾指针的值相同时表示队列空。
        （2）链式存储。用链表表示的队列简称为链队列。为了便于操作，给链队列添加一个头节点，并令头指针指向头节点。队列为空的判定条件是：头指针和尾指针的值相同，且均指向头节点。
        3）队列的应用
        队列结构常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
 
       数据类型
        基本数据类型是C++内部预先定义的数据类型，非基本数据类型是用户自己定义的数据类型。
        1）基本数据类型
        基本数据类型包括整型int、字符型char、逻辑型bool、无值型void、实型float、双精度型double，与C语言没什么差别。
        2）非基本数据类型
        非基本数据类型包括数组type［］、指针type*、结构struct、联合union、枚举enum和类class，比C语言增加了类class数据类型。
        3）new和delete
        （1）分配内存。
        在C语言中：char *name=（char*）malloc（Length+1）;。
        使用new: char *name=new char［Length+1］;。
        （2）释放内存。
        在C语言中：free（name）;。
        使用delete: delete［］name;。
 
       指针
        指针是C语言中最为重要也是最难的一个关键点，很多数据结构都是基于指针实现的，如链表、链式队列、链栈、二叉树等。
        所谓指针，就是一个用来存储地址的变量。这可谓指针的本质，需要牢记。
        也许你会很纳闷，指针为什么一定要定义成某类型（int、char）呢？指针不能就是"指针类型"吗？接触过汇编的人就很容易理解为什么。存储单元的单位是字节，就是说一般地址是按字节编址的，对一个地址进行操作（读取或赋值）就要指明是对单字节（不用特别声明）、两字节（WORD PTR），还是双字节（四字节，DWORD PTR）进行操作。同样，指针是存储地址的，即指针就是一个地址，自然也要说明其类型；而且，这个类型还关乎指针自加自减时真正加减的字节数。
        顺便说一下，数组名也是指针。数组在申请空间时，数组名存储该存储空间的首地址。注意：数组名存储的是地址，因此也是指针，只是该指针一旦赋值后就不能修改，即所谓常指针。当直接输出数组名时，输出的其实是数组的首地址。这样，当形参声明为指针时，亦可将数组名作为实参进行传递。因此，可以用指针的方式访问数组中的元素，如下例采用指针的方式遍历输出数组。
        
        当指针作为函数参数传递时，需要特别注意C语言中的"值"传递原则。下例中的函数希望为指针p申请空间，但不能达到目的，为什么呢？
        
        归根结底，C函数的形参与实参之间只是"值传递"：当形参是普通变量时，传递的是实参的值；当形参是指针时，传递的是指针变量的值，即某变量的地址，这样可以通过指针成功地改变其所指单元的值，但自身的改变不会传回给实参。上例可改为：
        
        注意：这样修改后，调用时实参应该是指针的"地址"（或指向指针的指针）。这样即上面所说的可以改变指针所指单元的值，因此可达到预期目的。
 
       基本操作
        Excel基本操作包括工作簿操作和工作表输入与输出。
               工作簿基本操作
               工作簿的基本操作包括新建工作簿、打开工作簿、保存工作簿和关闭工作簿。具体操作方法：选择“文件”→“新建”（或“打开”、“保存”、“关闭”）命令，在弹出的对话框中进行相应操作，单击“确定”按钮。
               工作表输入
               工作簿创建完成后，需要向单元格中输入数据，在Excel 2003的电子表格中，既可以输入数字，也可以输入汉字、英文、标点、特殊符号和公式等（若要输入中文文本，应先转换输入法，用Ctrl+Shift组合键可以改变中文输入法，用Ctrl+Space组合键可以进行中英文转换）。输入的方法有如下三种。
               .单击要输入数据的单元格，输入数据，按Enter键确认。
               .先单击选定单元格，再单击“编辑栏”的内容框，输入数据，通过单击“编辑栏”的输入按钮或取消按钮完成操作。
               .双击要输入数据的单元格，此单元格内会出现插入点，输入数据，按Enter键确认。（此方法主要用于单元格中数据的修改）
                      输入文本。
                      在Excel 2003中的文本是指字符集或数字和字符的组合，默认情况下文本向左对齐。当输入文本过长时，由于列宽所限，往往不能显示所有数据，可在单元格行或列的分界线处双击，Excel会自动调整行高或列宽，以最合适的宽度显示数据。若要在一个单元格内输入多行文本，可按Alt+Enter组合键换行。若要输入数字字符串，如身份证号、电话号码和邮政编码等，要在所输内容前加单引号“'”，以免被系统误认为是数值型数据。
                      输入数字。
                      数值型数据是最常见且最重要的数据类型，默认情况下数字向右对齐。当输入分数时，前面必须加0和空格。例如要输入“3/5”，应输入“0 3/5”，如果直接输入“3/5”，Excel会误认为是日期“3月5日”。输入负数时，可加“-”或（）。例如要输入“负5”，可输入“-5”或“（5）”。
                      输入日期和时间。
                      当在单元格中输入系统可识别的时间和日期数据时，单元格的格式会自动转换为相应的“时间”和“日期”格式，无需再次设定，默认情况下向右对齐。输入日期时，用“/”或“-”分隔，如2011年10月1日的输入形式是“11/10/1”或“11-10-1”（也可输入4位年份，如“2011/10/1”）。如要输入当前日期，可按Ctrl+；（分号）。输入时间时，用“：（冒号）”分隔时分秒，有12小时制，也有24小时制，若输12小时制，其后需加空格和A（上午）或P（下午），不加A或P时默认为上午。如要输入下午2：23：45，则输入“14：23：45”或“2：23：45 P”。
                      导入外部数据。
                      Excel 2003的兼容性很强，可以从很多外部来源导入数据，避免重复输入。操作时，先在工作表中选定要导入数据的单元格，再选择“数据”→“导入外部数据”→“导入数据”命令，打开“选取数据源”对话框作进一步设置即可。
                      自动填充数据。
                      在Excel中对具有规律性的数据可采用填充和自动填充的功能，避免逐个手动输入，提高输入效率，减少输入错误。例如在相邻的几个单元格中输入序列数字一、二、三、…，或星期一、星期二、…序列。Excel内置的序列数据有日期序列、时间序列和数值序列，用户可以根据需要创建自定义序列。填充时要注意鼠标的形状，鼠标有三种形状：
                      .（空心十字形）：鼠标呈空心十字形，拖曳鼠标的结果是选定区域。
                      .（实心十字形）：鼠标呈实心十字形，拖曳鼠标的结果是自动填充。
                      .（空心箭头形）：鼠标呈空心箭头形，拖曳鼠标的结果是移动对象。
                      .填充：选中单元格，选择“编辑”→“填充”命令，可按向上填充／向下填充／向左填充／向右填充／序列等方式填充。
                      自动填充：可使用填充柄自动填充数据。填充柄是指活动单元格或单元格区域右下角的黑色四方块。使用时，选中已有数据的单元格，如下图（a）所示的A1。用鼠标拖动填充柄可将已有数据填充至拖动位置复制单元格，如下图（b）所示。如要按序列填充，可在拖动完成后单击拖动区域右下角的“自动填充选项”按钮，选中“以序列方式填充”选项，如下图（c）所示。
                      
                      自动填充
                      自定义序列：选择“工具”→“选项”命令，打开“选项”对话框，选择“自定义序列”选项卡，在“自定义序列”列表框中列出了系统内置的序列，需要时，只要输入第一项后，用鼠标拖动填充柄就可以完成按序列形式填充内容的操作。
                      定义一个新序列：用户可以根据需要定义一个新序列。操作方法是在“输入序列”文本框中依次输入序列内容，并按Enter键分隔各项内容。编辑完新序列后，单击“添加”按钮。也可使用“导入”按钮添加已选定的数据序列。
               格式设置
               对创建好的工作表进行格式设置，包括单元格格式、条件格式和自动套用格式设置。通过设置可使表格更加美观，重点更加突出。
                      单元格格式设置。
                      可以使用“格式”工具栏上的功能按钮完成单元格设置；或者通过选择“格式”→“单元格”命令打开“单元格格式”对话框来完成单元格设置。“单元格格式”对话框中有6个选项卡，其功能如下所述。
                      .“数字”选项卡：可在“分类”列表框中选择数值类型，并对显示格式作进一步设置，如设置小数位数，日期的显示方式等。
                      .“对齐”选项卡：可对单元格中的数据对齐方式、文本方向等进行控制。
                      .“字体”选项卡：可对数据的字体、字型、字号、颜色等进行设置。
                      .“边框”选项卡：可对单元格区域的内、外边框进行设置。操作时，先选择线条的样式和颜色，再选择边框的类型。
                      .“图案”选项卡：可对单元格底纹的颜色和图案进行设置。
                      .“保护”选项卡：可对单元格的保护与隐藏进行设置。但单元格的保护与工作表的保护是联系在一起的，只有工作表处于保护状态时，单元格才能处于保护状态。
                      条件格式设置。
                      设置方法：先选定单元格区域，再选择“格式”→“条件格式”命令，系统显示“条件格式”对话框。设置条件表达式（最多能设置3项条件），并单击“格式”按钮，系统显示“单元格格式”对话框，设置满足条件的数据的显示格式。
                      条件格式设置的作用是根据指定的公式或数值来确定搜索条件，并将格式应用到符合条件的单元格区域中，目的是突出重点数据的显示。例如，在销售业绩表中，将销售业绩最高的单元格底纹设置成“绿色”，销售业绩最小的单元格底纹设置成“灰色”。
                      自动套用格式。
                      设置方法：选中单元格区域，选择“格式”→“自动套用格式”命令，打开“自动套用格式”对话框，选择所需样式。也可单击“选项”按钮，对某一格式作进一步设置。
               工作表的移动和复制
               在同一个工作簿中进行移动和复制工作表的方法有如下两种。
               （1）鼠标拖动法。用鼠标拖动要移动的工作表标签，移到合适的位置释放鼠标即可。复制工作表只要按住Ctrl键，然后拖动鼠标，即可以完成工作表的复制。
               （2）菜单法。选定要移动或复制的工作表，在选定的工作表标签上单击右键，在弹出的快捷菜单中选择“移动或复制工作表”命令，系统弹出“移动或复制工作表”对话框。在此对话框中先选择被移动或复制的工作表要放的位置，再单击“确定”按钮。如果选定对话框下边的“建立副本”复选框，则是复制操作，否则是移动操作。
               若要移动或复制工作表到另一个工作簿，则在选定要移动或复制的工作表后接着打开目标工作簿，然后在“移动或复制工作表”对话框中选择目标工作簿。
               工作表的输出
               在实际工作中，为了便于查看和保存，建立好的工作表往往需要按要求打印出来。完成工作表打印通常进行页面设置和打印范围设置。
               （1）进行打印预览。如果对打印预览的效果不满意，可对工作表重新编辑修改，然后再次进行打印预览，直至满意。
               （2）打印输出。
               由于上述操作方法与Word操作方法一致，故不再赘述。
 
       空指针
        标准预处理宏NULL（它的值为0，称为空指针常量）常用来表示指针不指向任何内存单元，可以把NULL赋给任意类型的指针变量，以初始化指针变量。例如：
        
        需要注意：全局指针变量会被自动初始化为NULL，局部指针变量的初始值是随机的。编程时常见的一个错误是没有给指针变量赋初值。未初始化的指针变量可能表示了一个非法的地址，导致程序运行时出现内存访问错误，从而使程序异常终止。
 
       排序
        假设含n个记录的文件内容为｛R1，R2，…，Rn｝，其相应的关键字为｛k1，k2，…，kn｝。经过排序确定一种排列｛Rj1，Rj2，…，Rjn｝，使得它们的关键字满足如下递增（或递减）关系：kj1≤kj2≤…≤kjn（或kj1≥kj2≥…≥kjn）。
 
       拓扑排序
               AOV网
               在工程领域，一个大的工程项目通常被划分为许多较小的子工程（称为活动），当这些子工程都完成时，整个工程也就完成了。若以顶点表示活动，用有向边表示活动之间的优先关系，则称这样的有向图为以顶点表示活动的网（Activity On Vertex network，AOV网）。在有向网中，若从顶点νi到顶点νj有一条有向路径，则顶点νi是νj的前驱，顶点νj是νi的后继。若<νi，νj>是网中的一条弧，则顶点νi是νj的直接前驱，顶点νj是νi的直接后继。AOV网中的弧表示了活动之间的优先关系，也可以说是一种活动进行时的制约关系。
               在AOV网中不应出现有向环，若存在的话，则意味着某项活动必须以自身任务的完成为先决条件，显然这是荒谬的。因此，若要检测一个工程划分后是否可行，首先就应检查对应的AOV网是否存在回路。检测的方法是对其AOV网进行拓扑排序。
               拓扑排序
               拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点νi到νj有一条路径，则在该线性序列中，顶点νi必然在顶点νj之前。
               一般情况下，假设AOV网代表一个工程计划，则AOV网的一个拓扑排序就是一个工程顺利完成的可行方案。对AOV网进行拓扑排序的方法如下：
               （1）在AOV网中选择一个入度为零（没有前驱）的顶点且输出它；
               （2）从网中删除该顶点以及与该顶点有关的所有边；
               （3）重复上述两步，直至网中不存在入度为零的顶点为止。
               按照上述步骤进行拓扑排序的过程如下图所示，得到的拓扑序列为6，1，4，3，2，5。显然，对有向图进行拓扑排序所产生的拓扑序列有可能是多种。
               
               拓扑排序过程
               执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。
   题号导航      2025年上半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第3题    在手机中做本题